백준 10942번 - 팰린드롬?

문제

백준 10942번 - 팰린드롬?

아이디어

• 가장 단순한 방법은 M개의 질문마다 계산하는 것이다. 하지만 이는 O(N x M)으로 비효율적이다.
• M개 질문을 받기 전에 미리 길이가 1~N의 팰린드롬을 구해놓으면 계산없이 바로 출력할 수 있다.
• 우선 길이가 1이면 무조건 팰린드롬이고, 길이가 2면 같은 수가 연속해서 나왔을 때 팰린드롬이다.
• 길이가 3일때 부터는 DP로 값을 채울 수 있다.
• 첫번째 수가 마지막 수와 같고, 간격을 한칸씩 줄였을 때의 범위도 팰린드롬이면 해당 길이는 팰린드롬을 만족한다.
• 예를 들어 1~4, 길이 4의 팰린드롬을 구할 때 1번째와 4번째의 수가 같고, 2번째와 3번째가 팰린드롬이면 1~4 범위는 팰린드롬이다.

예상 시간 복잡도

• 수열의 크기 N
• 예상 시간 복잡도 : O(N^2)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_10942 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        boolean[][] palindrome = new boolean[n][n];

        //길이가 1~2인 팰린드롬 확인
        for (int i = 0; i < n; i++) {
            palindrome[i][i] = true;
            if (i < n - 1) {
                if (arr[i] == arr[i + 1]) {
                    palindrome[i][i + 1] = true;
                }
            }
        }

        //길이가 3~N인 팰린드롬 확인
        for (int s = n - 3; s >= 0; s--) {
            for (int e = s + 2; e < n; e++) {
                if (arr[s] == arr[e] && palindrome[s + 1][e - 1]) {
                    palindrome[s][e] = 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()) - 1;
            int e = Integer.parseInt(st.nextToken()) - 1;

            sb.append(palindrome[s][e] ? 1 : 0).append("\n");

/*          //비효율적인 방법
            boolean isPalindrome = true;

            while (s < e) {
                if (arr[s] != arr[e]) {
                    isPalindrome = false;
                    break;
                }
                s++;
                e--;
            }

            sb.append(isPalindrome ? 1 : 0).append("\n");
*/
        }

        System.out.print(sb);
    }
}

• 비효율적인 방법

• DP