BOJ 17609 회문

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

문제

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다.

---

입력

입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

---

출력

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

---

예제 입력 1

7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc

예제 출력 1

0
1
1
2
2
0
1

---

코드

투 포인터를 이용해서 주어진 문자열이 회문인지 검사하는 문제였다.

처음 문제를 풀 때 반례에 대해 크게 생각해보지 않아서 틀렸었다.

xbabbax와 같은 문자열을 검사해보면, xbabbax 이부분에서 서로 다른 문자를 검사하게 된다.

이때 왼쪽 포인터와 오른쪽 포인터 각각 다음 위치로 넘겨도 다음과 같이 xbabbax, xbabbax 모두 동일한 문자가 등장하지만, 왼쪽 포인터를 다음으로 넘긴 케이스만 회문 검사를 통과하게 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            String input = br.readLine();
            int result = checkPalindrome(input, 0, input.length() - 1, false);
            answer.append(result).append('\n');
        }

        System.out.println(answer);
    }

    static int checkPalindrome(String input, int leftIdx, int rightIdx, boolean removed) {
        while (leftIdx < rightIdx) {
            if(input.charAt(leftIdx) == input.charAt(rightIdx)) {
                leftIdx++;
                rightIdx--;
            } else if(removed) {
                return 2;
            } else {
                return Integer.min(
                        checkPalindrome(input, leftIdx, rightIdx - 1, true),
                        checkPalindrome(input, leftIdx + 1, rightIdx, true)
                );
            }
        }

        if(removed) {
            return 1;
        }

        return 0;
    }
}