백준 17609 회문

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

 

#include <iostream>

using namespace std;


string str;

int check(int l, int r, bool palin) {
    while (l < r) {
        if (str[l] != str[r]) {
            if (palin) {
                if (check(l + 1, r, false) == 0 || check(l, r - 1, false) == 0) return 1;
            }
            return 2;
        }
        l++; r--;
    }
    return 0;
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;

    for (int test = 0; test < t; test++) {


        cin >> str;
        cout << check(0, str.size() - 1, true) << "\n";

    }

    return 0;
}

 

 투 포인터 문제이다. 입력을 받고, 회문, 유사회문, 나머지를 판별하는 코드를 작성하는 문제이다. 

 

풀이

int check(int l, int r, bool palin) {
    while (l < r) {
        if (str[l] != str[r]) {
            if (palin) {
                if (check(l + 1, r, false) == 0 || check(l, r - 1, false) == 0) return 1;
            }
            return 2;
        }
        l++; r--;
    }
    return 0;
}

 

 우선 문자열의 맨 앞과 맨 뒤부터 가운데로 포인터를 옮기면서 문자를 하나씩 비교해 간다. palin에는 팰린드롬 여부가 들어간다. 문자를 비교하다 다른 문자가 온다면 두 가지로 나누어질 수 있다.

 

 1. 왼쪽의 문자를 제거하면 회문이 되는 경우

 2. 오른쪽의 문자를 제거하면 회문이 되는 경우

 

둘 중 하나의 조건을 충족할 경우 유사회문이므로 1을 출력한다. 그러나 팰린드롬이 아님이 확정이 난 후에 또 왼쪽과 오른쪽의 문자가 다를 경우 2를 출력한다. 문제가 없다면 회문이므로 0을 출력한다.