[Java] BOJ 17609 회문

[Java] BOJ 17609 회문

 

www.acmicpc.net/problem/17609

17609번: 회문

 

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

public class BOJ_17609_회문 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		for (int i = 0; i < T; i++) {
			String s = br.readLine();
			MIN = 2;
			checkPal(false, s, 0, s.length()-1);
			System.out.println(MIN);
		}
	} // main

	static int MIN;
	static void checkPal(boolean isUse, String s, int start, int idx) {
		for (int i = start; i < s.length(); i++) {
			if (i >= idx) {
				break;
			}
			if (s.charAt(i) != s.charAt(idx)) {
				if (isUse) return;
				if (s.charAt(i) == s.charAt(idx - 1)) {
					checkPal(true, s, i+1, idx-2);
				}
				if (MIN == 2 && s.charAt(i + 1) == s.charAt(idx)) {
					checkPal(true, s, i+2, idx-1);
				}
				return;
			}
			idx--;
		}
		if (isUse) MIN = 1;
		else MIN = 0;
		return;
	}
}

 

... 어렵지 않은데 이런 저런 이유로.. 시간이 오래 걸렸다.

슬프다

 

양쪽에서 인덱스를 좁혀오면서 같은 지 확인하는데,

만약 같지 않고 아직 삭제한 적도 없다면 checkPal() 함수를 재귀 타고 들어가서 끝까지 도달하는 지 확인한다.

 

이미 유사회문 판정이 났다면 MIN == 2 이걸로 더이상 유사회문 판정을 하지 않는다.

 

회문 판정 끝까지 도달 했을 때 삭제한 적이 있으면 MIN = 1

없으면 0

으로 출력한다.