[백준/JAVA] 10942_팰린드롬?

백준🔗

10942번: 팰린드롬?

 

문제

 

 

간단 풀이

팰린드롬하면

처음과 끝 비교, 앞에서 2번째와 뒤에서 2번째 비교....

아니면 StringBuilder에 쌓아서 reverse 한 다음에 같은지 비교

이런 방법들이 떠올랐는데 이번 문제에서는 수열의 크기가 최대 2000, 질문 개수가 최대 100만이기 때문에 매번 일일이 비교하면 최악의 경우 1000 * 100만 = 10억  => 약 10초(?)🤯😨 

너무나도 시간초과다..

 

한 번 팰린드롬 여부를 판단한 것에 대해 그 결과를 그보다 긴 수열의 팰린드롬 여부 판단에 재사용 하도록 하는 방식으로 DP를 사용해서 해결했다.

어떤 수열이 있을 때 양옆으로 같은 수를 붙여주면 새롭게 만들어진 수열도 팰린드롬이 된다

라는 원리를 사용한 것이다.

(사실 바로 떠오르지 않아서 고민하다가 구글에게 도움을 좀 받았다..ㅎㅎ)

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine()); // 수열 크기
		int[] arr = new int[N + 1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		// 길이가 1인 경우부터 시작해서 팰린드롬인지 여부를 dp로 먼저 저장해두기
		boolean[][] palindrome = new boolean[N + 1][N + 1];
		// 길이 1인 경우
		for (int i = 1; i <= N; i++) {
			palindrome[i][i] = true;
		}
		// 길이 2인 경우
		for (int i = 1; i <= N - 1; i++) {
			if (arr[i] == arr[i + 1]) {
				palindrome[i][i + 1] = true;
			}
		}
		// 길이가 3이상인 경우
		for (int d = 3; d <= N; d++) {
			for (int i = 1; i <= N - d + 1; i++) {
				if (arr[i] == arr[i + d - 1] && palindrome[i + 1][i + d - 2]) {
					// 1) 양쪽 끝이 같고
					// 2) 그 사이도 팰린드롬이면
					// 팰린드롬이다!
					palindrome[i][i + d - 1] = true;
				}
			}
		}

		int M = Integer.parseInt(br.readLine()); // 질문 개수
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int S = Integer.parseInt(st.nextToken()); // 시작
			int E = Integer.parseInt(st.nextToken()); // 끝
			if (palindrome[S][E]) {
				bw.write("1");
				bw.write("\n");
			} else {
				bw.write("0");
				bw.write("\n");
			}
		}
		bw.flush();
		br.close();
		bw.close();
	}
}

 

참고 자료

백준 10942 팰린드롬? JAVA