[Algorithm] 팰린드롬?

이번 문제는 주어진 수열에서 입력으로 주어진 범위가 팰린드롬이 맞는지를 확인하는

문제이다. 이번 문제는 해결하는데 꽤나 오래 걸렸다. 처음엔 방법을 몰라 헤맸었지만

전처리를 한 후 쿼리 형식으로 해결을 하였다. 전처리를 하는데 필요한 시간은

O(n^2)이고 그 외 쿼리 처리에 대한 시간은 O(1)이다.

해결 방법은 다음과 같다. 2차원 배열 C에 C[start][end]의 팰린드롬 유무를 저장한다.

그렇게 하기 위해선 C[start+1][end-1]이 팰린드롬인지를 검사하고 입력된 값인

arr[start] == arr[end]의 조건도 성립해야만한다.

정리하자면 아래와 같다.

1. 수열인 arr[start] == arr[end] 인지
2. 그 다음 C[start][end] = C[start+1][end-1]인지를 검사한다.

위와 같은 방법으로 해결 하면 끝!

Source:

import java.io.*;

import java.util.*;

public class a_10942 {

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());

int M = Integer.parseInt(br.readLine());

int[][] C = new int[N + 1][N + 1];

for (int i = 1; i <= N; i++) C[i][i] = 1; //길이가 1인 palindrome

for (int i = 1; i <= N; i++) {

for (int j = 1; j + i <= N; j++) { // i는 거리 , j는 start point

if (i == 1) {

if (arr[j + 1] == arr[j]) C[j][j + 1] = 1;

} else {

if ((arr[i + j] == arr[j]) && (C[j + 1][i + j - 1] == 1)) C[j][j + i] = 1;

}

}

}

for (int i = 0; i < M; i++) {

st = new StringTokenizer(br.readLine(), " ");

bw.write(C[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())]+"\n");

}

bw.close();

}

}