백준 17609 회문 (C++)

17609번: 회문

투 포인터를 이용한 문제이다. 입력받은 문자열을 반복문을 돌면서 회문인지 확인을 해준다. 만약 start와 end를 비교하고 만약 같지 않을 경우 start + 1 을 했을 때와 end - 1을 했을 때 둘 중 회문이 있는지 비교를 해주고 만약 있다면 1을 리턴해준다. 없다면 2를 리턴해주고 모두 같을 경우 0을 리턴을 해주고 이를 출력해준다. 생각보다 어려웠던 문제였다. 단순히 스택 형식으로 접근했다가 로직에 문제가 생겨 많이 해맸었다. 투 포인터에 대해 잘 기억해두자.

#include <iostream>
#include <vector>

using namespace std;

int T;
string S[30];

int palindrome(string s, int start, int end, int count) {
    while (start <= end) {
        if(s[start] != s[end]) {
            if (count < 1) {
                if (!palindrome(s, start + 1, end, count + 1) || !palindrome(s, start, end - 1, count + 1)) {
                    return 1;
                }
            }
            
            return 2;
        }

        start++;
        end--;
    }

    return 0;
}

void solution() {
    for (int i = 0; i < T; i++) {
        cout << palindrome(S[i], 0, S[i].size() - 1, 0) << "\n";
    }
}

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

    cin >> T;

    for (int i = 0; i < T; i++) {
        cin >> S[i];
    }

    solution();

    return 0;
}