[BOJ/C++] 회문(17609번)

1. 개요

https://www.acmicpc.net/problem/17609

17609번: 회문

1-1. 설명

회문(팰린드롬)은 앞뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 여기서 그 자체는 회문이 아니나, 한 문자를 삭제해 회문으로 만들 수 있는 문자열이라면 유사 회문이라 부른다. 우리는 제시된 문자열을 분석해 그것이 회문인지, 유사 회문인지, 일반 문자열인지 판단한다. 회문이면 0, 유사 회문이면 1, 그 외는 2를 출력한다. 

1-2. 제한 사항

 - 첫 줄에는 문자열 개수를 나타내는 정수 T가 주어지며, 1 이상 30 이하

 - 다음 줄부터 T개 줄에 걸쳐 한줄에 하나의 문자열이 입력으로 주어지며, 길이는 3 이상 100,000 이하

 - 문자열은 영문 알파벳 소문자로만 이루어짐

---

2. 구현

2-1. 풀이

start, end 인덱스를 두어 확인하였다. 여기서, 문자가 다르면 남은 문자열의 앞, 뒤 문자를 빼고 팰린드롬을 확인한다. 팰린드롬이 이루어지면 1을 저장하고 유사 팰림드롬 또한 되지 않으면 2를 저장한다. 처음에 너무 복잡하게 생각해서 코드가 복잡했으나, 위 방법대로 차근차근 풀면 쉽게 풀리는 문제였다. 

2-2. 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T, start, end, resIdx = 0;
    string str, leftStr, rightStr;
    cin >> T;

    for (int tc = 0; tc < T; tc++) {
        cin >> str;
        start = 0, end = str.size() - 1, resIdx = 0;
        for (int i = 0; i < str.size() / 2; i++) {
            if (str[start] != str[end]) { // 알파벳이 다를 때
                int curSize = end - start + 1;

                // 현재 위치 기준 start 인덱스 제외 남은 알파벳 회문 확인
                leftStr = str.substr(start + 1, curSize / 2);
                rightStr = str.substr(end - curSize / 2 + 1, curSize / 2);
                reverse(rightStr.begin(), rightStr.end());
                if (leftStr == rightStr) resIdx = 1;

                // 현재 위치 기준 end 인덱스 제외 남은 알파벳 회문 확인
                leftStr = str.substr(start, curSize / 2);
                rightStr = str.substr(end - curSize / 2, curSize / 2);
                reverse(rightStr.begin(), rightStr.end());
                if (leftStr == rightStr) resIdx = 1;

                if (resIdx == 0) resIdx = 2; // 유사 회문이 되지 않을 때
                break;
            }
            else {
                start += 1;
                end -= 1;
            }
        }
        cout << resIdx << "\n";
    }
    
    return 0;
}