BOJ 17609 : 회문

문제링크

풀이요약

투 포인터

풀이상세

유사회문인지 아닌지를 판별하는 방법은 다음과 같다.

1. 시작값과 끝값을 지정하고, $l<r$ 동안 탐색을 지정한다. 문자가 홀수 일 경우 가운데는 탐색할 필요가 없으므로, $l<r$ 범위에서 문자열에 대한 회문 검증이 가능하다.

2. 만약 임의의 $l,r$ 값이 서로 문자가 맞지 않는 경우를 비교하여 $l+1$, $r-1$ 한 경우를 다시 탐색하게 한다.

3. 다시 탐색했음에도 $l,r$ 값이 서로 다른 문자를 나타낸다면 그때는 유사회문도 아닌 것이다.

#include <iostream>
using namespace std;
int N;

int go(string str, int l, int r, bool check) {
    while (l < r) {
        if (str[l++] != str[r--]) {
            if (check) {
                if (go(str, l, r + 1, false) == 0) return 1;
                else if (go(str, l - 1, r, false) == 0) return 1;
            }
            return 2;
        }
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N;
    string str;
    for (int i = 0; i < N; i++) {
        cin >> str;
        cout << go(str, 0, str.size() - 1, true) << "\n";
    }
}