[백준/java] 17609번 회문

• 문제 : https://www.acmicpc.net/problem/17609
• 분류 : 투포인터 
• 시간초과를 해결하기 위해 check가 2 이상인 경우는 바로 2를 리턴해준다. 이미 회문, 유사회문이 아닌 것으로 판정났으니 더이상 재귀함수를 호출하지 않도록.
• 풀이방법 : 투포인터로 문자열의 맨앞부터 시작, 문자열의 맨뒤부터 시작해서 서로 비교한다. 만약 서로 다른 구간이 발생하면 그 앞뒤로 비교하도록 하고, 만약 앞뒤로 비교했을 때 회문으로 충족된다면 유사회문으로 볼 수 있다.

package boj.string;

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

/**
 * @문제명 회문
 * @분류 투포인터, 문자열
 */
public class BOJ17609 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        String[] arr = new String[n];
        for (int i = 0; i < n; i++) {
            arr[i] = br.readLine();
        }

        for (int i = 0; i < n; i++) {
            String current = arr[i];
            System.out.println(palindrome(0, current.length() - 1, current, 0));
        }
    }

    private static int palindrome(int s, int e, String s1, int check) {
        // 시간초과를 해결하기 위해 아래 조건을 추가함
        if(check >=2) return 2;

        while (s < e) {
            if (s1.charAt(s) == s1.charAt(e)) {
                s++;
                e--;
            } else {
                return Math.min(palindrome(s + 1, e, s1, check + 1), palindrome(s, e - 1, s1, check + 1));
            }
        }
        return check;
    }
}