[C++][백준 17609] 회문

문제

접근 방법

투 포인터를 활용하면 된다. 만약 도중에 동일하지 않은 경우를 만나면 왼쪽을 옮기는 방법, 오른쪽을 옮기는 방법으로 경우를 나누면 된다.

코드

#include <iostream>
using namespace std;
int T, answer;
string str;
void checkPalindrome(int left, int right, bool isPseudo)
{
    int cnt = 0;
    while (left < right)
    {
        if (str[left] == str[right]) // 동일한 경우
        {
            ++left, --right;
        }
        else
        {
            if (isPseudo) // 이미 제거한 경우
            {
                if (answer == 3)
                {
                    answer = 2;
                }
                return;
            }
            checkPalindrome(left + 1, right, true);
            checkPalindrome(left, right - 1, true);
            return;
        }
    }
    answer = isPseudo;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> str;
        answer = 3;
        checkPalindrome(0, str.size() - 1, false);
        cout << answer << "\n";
    }
    return 0;
}

풀이

재귀 함수가 깊이 있게 호출될 일은 없어서 걱정할 필요는 없다.

ababbabaa와 같이 당장에는 어느 한쪽을 없애기 판단하기 힘든 경우가 존재해서 재귀 함수를 사용했다.