[BOJ] 10942 팰린드롬? - JAVA

1. 문제

10942번: 팰린드롬?

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.
먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.
각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.
예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.
S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
S = 3, E = 3인 경우 1은 팰린드롬이다.
S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.
자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

---

2. 풀이

N, 배열 입력

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
int[] arr = new int[N];
StringTokenizer st = new StringTokenizer(in.readLine());
for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());

 

길이 <= 2 팰린드롬 파악

[N][N]칸 boolean 배열을 만든다.

[start][end]칸에 start부터 end까지가 팰린드롬이라면 true, 아니라면 false를 저장한다.

먼저 길이 2 미만인 팰린드롬을 파악한다.

길이가 1이라면 무조건 팰린드롬이고, 길이가 2라면 양 옆 두 개를 비교해서 같을 때가 팰린드롬이다.

boolean[][] dp = new boolean[N][N];
for(int i=0;i<N;i++){
   dp[i][i] = true;
   if(i+1<N && arr[i]== arr[i+1]) dp[i][i+1] = true;
}

 

길이 > 2 팰린드롬 파악

길이를 2부터 N-1까지 하나씩 늘려가면서 팰린드롬을 파악한다. 이때 길이를 2부터 잡는 이유는 start위치를 제외한 길이이기 때문이다. (사실상 3)

길이별로 start를 0부터 N-len까지 탐색한다.

시작과 끝점(start+len)이 같고 dp[시작 다음점][끝 이전 점]이 팰린드롬이라면 dp[start][start+len]도 팰린드롬이다.

start와 start+len사이가 팰린드롬인 것을 확인하려면 dp[start+1][start+len-1]을 보면 된다. (표에서 o체크 부분)

start	start+1	start+2	start+3=start+len-1	start+4=start+len(끝)
같음	o	o	o	같음

for(int len=2;len<N;len++){
   for(int start=0;start<N-len;start++){
      if(arr[start]==arr[start+len] && dp[start+1][start+len-1]) dp[start][start+len] = true;
   }
}

 

M개의 S,E쌍 입력 & 출력

StringBuilder를 활용해서 출력한다.

이 코드의 dp는 인덱스가 0부터 시작하는데 문제에서 주어지는 입력은 인덱스가 1부터 시작하는 것만 주의하면 된다.

int M = Integer.parseInt(in.readLine());
StringBuilder sb = new StringBuilder();
for(int i=0;i<M;i++){
   st = new StringTokenizer(in.readLine());
   if(dp[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1]) sb.append("1\n");
   else sb.append("0\n");
}
System.out.print(sb);

 

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_10942_팰린드롬 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      int[] arr = new int[N];
      StringTokenizer st = new StringTokenizer(in.readLine());
      for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());

      boolean[][] dp = new boolean[N][N];
      for(int i=0;i<N;i++){
         dp[i][i] = true;
         if(i+1<N && arr[i]== arr[i+1]) dp[i][i+1] = true;
      }

      for(int len=2;len<N;len++){
         for(int start=0;start<N-len;start++){
            if(arr[start]==arr[start+len] && dp[start+1][start+len-1]) dp[start][start+len] = true;
         }
      }

      int M = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();
      for(int i=0;i<M;i++){
         st = new StringTokenizer(in.readLine());
         if(dp[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1]) sb.append("1\n");
         else sb.append("0\n");
      }
      System.out.print(sb);
   }
}

---

3. 결과