[JAVA]BOJ 17609, 회문

처음에 시간초과가 날게 뻔하지만 O(n^2)로 풀고, 시간초과 받고.. 다시 풀었다.

 

'유사회문'을 확인하는게 좀 어렵다. 유사회문을 확인하는 방법은

 

1. 순서대로 Palindrome을 확인하다가 달라지는 순간이 왔을때

2-1. 왼쪽을 하나 증가시키고 Palindrome인지 확인한다.

2-2. 오른쪽을 하나 감소시키고 Palindrome인지 확인한다.

3. 2-1, 2-2인 경우 Palindrome이 아니면 유사회문도 아니므로 2를 출력한다.

 

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

public class BOJ17609 {
    public static int isPalindrome(char[]arr, int left, int right){
        while(left < right){
            if(arr[left] != arr[right])
                return 0;
            left++;
            right--;
        }
        return 1;
    }

    public static int checkPalindrome(char[] arr){
        int left = 0, right = arr.length - 1, result = 0;

        while(left < right ) {
            if(arr[left] != arr[right]){
                if((isPalindrome(arr, left + 1, right) == 1) // 유사회문인지 확인
                       || (isPalindrome(arr, left, right - 1) == 1))
                    result = 1;
                else
                    result = 2;
                break;
            }
            else{
                left++;
                right--;
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T, i;
        String str;

        T = Integer.parseInt(br.readLine());

        for(i=0;i<T;i++){
            str = br.readLine();
            System.out.println(checkPalindrome(str.toCharArray()));
        }
    }
}