[JAVA]백준10942번 팰린드롬?

문제는 다음과 같다.

오늘은 백준10942번 팰린드롬? 문제를 풀어보도록 하자. 문제 그대로 팰린드롬에 관한 문제이다. 팰린드롬이 궁금하다면 클릭해보자.

위 문제를 보면 시간제한이 굉장히 빡빡한 것을 알 수 있다. (무려 0.5초..) 그리고 질문이 무려 100만개이다. 따라서 질문이 하나하나 들어올 때마다 팰린드롬을 구현하는 것은 매우 비효율적이고 TLE가 날 확률이 매우매우 높다!

따라서 DP로 팰린드롬을 구현하고 질문이 들어올 때 마다 답을 해야한다. 즉, 질문이 1 3이 들어왔다면 1부터 3까지의 문장이 팰린드롬입니까?를 물어보는 것이고 우리는 dp[1][3]을 보고 True,False를 파악한 후 True면 1, False면 0을 출력하면 된다.

그리고 질문이 100만개이기 때문에 BufferedWriter를 써서 출력시간을 줄여주는 것이 좋다.

로직은 다음과 같이 짜보았다.

1. 우선 길이가 0인, 즉, 1 2 3 1 2 1이라면 1,2,3,1,2,1씩 인 것들은 dp[1][1],dp[2][2]…,dp[6][6] = true로 저장해주었다.
2. 길이가 1인 것들도 따로 저장해 주었는데 1,2,3,1,2,1이라면 1,2 / 2,3 / 3,1 / 1,2/ 2,1로 나눌 수 있고 dp[1][2], dp[2][3]…,dp[5][6] 까지 팰린드롬인 것을 True, False 나누어서 저장해주었다.
3. 그 후 3이상인 것들은 길이, 시작지점을 나타내는 2중포문을 이용해서 저장해주었다.
4. 예를 들어 dp[3][6]이라면 dp[4][5]가 팰린드롬인지 확인 && Number[3] == Number[6]인지만 확인해보면 알 수 있다. 이런 식으로 로직을 짰다.

                                     [코드]
package BaekJoon;

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

public class Main_10942 {
    static int N,M;
    static boolean dp[][];
    static String Number[];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        dp = new boolean[N+1][N+1];
        Number = new String[N+1];

        for(int i=1;i<=N;i++){
            Number[i] = st.nextToken();
        }

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

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            if(dp[from][to]){
                bw.write("1");
            }
            else{
                bw.write("0");
            }
            bw.newLine();
        }
        bw.close();
    }
    static public void Palindrome(){
        for(int i=1;i<=N;i++){//1개일 때는 무조건 팰린드롬
            dp[i][i] = true;
        }
        for(int i=2;i<=N;i++){//2개일 때 따로 파악
            if(Number[i-1].equals(Number[i])){
                dp[i-1][i] = true;
            }
            else{
                dp[i-1][i] = false;
            }
        }
        //3개 이상일 때
        for(int i=2;i<=N-1;i++){//길이
            for(int j=1;j+i<=N;j++){//시작하는 곳
                if(Number[j].equals(Number[j+i]) && dp[j+1][j+i-1]){
                    dp[j][j+i] = true;
                }
            }
        }
    }
}