백준 17609 - 회문

이번 문제는 백준의 골드 5 문제 회문 문제이다.
회문(palindrome)을 이용한 문제는 굉장히 많기 때문에,
문제가 풀만하다는 생각이 먼저 드는데 한 번 읽어보자.

최대 100000길이의 문자열이 최대 30개 주어진다.
이 때 회문이면, 정수 0을 반환하도록 한다.
이 때 한 글자를 빼서 회문을 만들 수 있으면 유사 회문으로 1을 반환한다.
이 때 한 글자 이상 다르면, 아무것도 아니므로 2를 반환한다.
이 문제를 어떻게 해결할 수 있을까?

투 포인터

가장 먼저 든 생각은 두 개의 포인터를 사용하는 것이다.
하나는 시작 위치에 나머지 하나는 마지막 위치에 둬보자.
이제부터 문자가 같은 지 다른 지 훑도록 해보자.

예를 들어 abbaa 라는 문자열이 있다.

  1. Left a, Right a
    두 문자가 동일하다.
    그럼 회문의 가능성이 있으므로 한 칸씩 안으로 옮기자.

  2. Left b, Right a
    두 문자가 다르다.
    이 때, 양쪽의 포인터를 하나씩 줄여보며 확인을 해야 한다.
    Right를 하나만 줄였을 때, b b로 문자가 같으므로, 회문 카운트를 하나 올리고 Right를 하나 줄인다.

  3. Left b, Right b 두 문자가 동일하다. 회문의 가능성이 있으므로 한 칸씩 안으로 옮긴다. 이 때, Left가 Right보다 커지므로 반복문을 종료한다.

올라간 회문 카운트는 1이므로, 이는 유사회문이다.
위와 같은 알고리즘으로 문제를 풀어나가려 했다.

반례

하지만 abbab를 한 번 생각해보자.
처음의 a와 b가 달라서 두 포인터 중 하나를 옮기려 하니,
Right를 앞으로 한 칸 당기는 경우엔 유사회문으로 판단된다.
하지만 Left가 뒤로 가는 경우엔 b a로 아무것도 아니게 된다.

무작정 Right를 앞으로 옮기기엔, babba와 같은 문자열이
또 다시 예외 사항으로 앞길을 막게 될 것이다.
이런 경우에, 어떻게 판단을 내릴 수 있을까?

내부 함수 호출

나는 단 한 글자만 달라야 유사 회문이라는 점에 초점을 두었다.
만약 위의 예시처럼 두 문자가 다른 경우, 새로운 함수를 호출한다.
현재 시점으로 부터 다시 회문을 확인하는 함수인데, 아래와 같이 구현했다.

int check_inner_palindrome(int left, int right) {
    while (left < right) {
        if (target[left] == target[right]) {
            left++;
            right--;
            // 같으면 그냥 계속 줄이면 됨
        }

        if (target[left] != target[right]) 
            return 2;
        // 다른게 한 번 더 나와버리면
    }

    return 1;
    // 정상적으로 종료되면 유사회문.
}

다르다고 판단된 문자에 대해, 위의 함수를 아래와 같이 호출한다.

int check_palindrome() {
    int left = 0, right = target.size() - 1, count = 9999;
    while (left <= right) {
        if (target[left] == target[right]) {
            left++;
            right--;
        // 같으면 그냥 계속 줄이면 됨
        }

        if (target[left] != target[right]) {
            // 둘이 다르다면?
            if (target[left + 1] == target[right])
                count = min(count, check_inner_palindrome(left + 1, right));
            if (target[left] == target[right - 1])
                count = min(count, check_inner_palindrome(left, right - 1));
            // 위의 경우들은 하나를 줄였을 때, 회문이 되는 경우

            if ((target[left + 1] != target[right]) && (target[left] != target[right - 1]))
                return 2;
            // 해당 경우는 양 쪽 하나씩 다 줄여봐도 다른 경우
            // 더 이상 탐색할 필요가 없음.

            return count;
        }
    }

    return count;
}

위에서 언급했던 예시인 abbab와 같이,
왼쪽을 줄였을 때, 오른쪽을 줄였을 때 모두 같은 문자인 경우라면?
두 경우 모두 함수를 호출해 회문인지를 판단하도록 한다.

만약 둘 중 하나라도 회문이 가능하다면 이 문자열은 유사회문이다.
따라서, count에 2보다 작은 1이 저장될 것이다.
위와 같이 구현하면, 어떤 경우에도 판단이 가능하다.