[백준 알고리즘/C++/그리디] 17609 회문

 

 

입력된 문자열이 회문, 유사회문, 둘다X 중 어디에 해당하는지 찾는 문제

 

 

문자열의 양 끝에서 부터 비교해오면 되는데

1. 모두 일치할 경우

2. 유사회문이 아닐 경우

3. 유사회문일지도 모르는 경우 → 일치하지 않는 지점부터 양쪽 문자 하나씩 번갈아 빼보며 다시 비교

이 순서로 판별하면 된다

시간제한이 있는 문제이므로 가지치기가 매우 중요하다

 

2번에서 하나를 뺀 나머지 문자열이 회문인 경우에 유사회문이 된다

회문이 아닐 경우에만 비교하도록 조건을 설정하여 시간을 줄여야하고 (코드 26번째 줄)

여기서 유사회문인지 아닌지가 판별되면 break 해줘서 시간을 줄여야한다 (코드 40번째 줄)

 

 

#include <iostream>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    string str;
 
    cin >> t;
    while (t--) {
        cin >> str;
 
        int res = 0;
        for (int i = 0, j = str.size() - 1; i < j; i++, j--) {
            if (str[i] == str[j]) continue;
 
            //유사회문일 가능성이 없으면
            if (str[i] != str[j - 1] && str[i + 1] != str[j]) {
                res = 2;
                break;
            }
 
            bool isPalindrome = false;
            for (int k = 0; k <= 1 && isPalindrome == false; k++) {
                int start = i, end = j;
                k == 0 ? start++ : end--; //하나씩 번갈아가며 빼기
 
                isPalindrome = true;
                for (int a = start, b = end; a < b; a++, b--) {
                    if (str[a] != str[b]) {
                        isPalindrome = false;
                        break;
                    }
                }
            }
 
            res = isPalindrome ? 1 : 2;
            break;
        }
 
        cout << res << "\n";
    }
}