[BOJ] 10942. 팰린드롬? - Java

10942.팰린드롬? : https://www.acmicpc.net/problem/10942

문제 설명

정수형 배열이 주어지고 홍준이가 명우에게 한 질문 S와 E 사이의 값이 팰린드롬인지 판단한다.

문제 접근

문제는 매우 간단하다. 팰린드롬은 즉 해당 배열이 대칭인지를 묻는 것이다. 기존에 투포인터로 접근해 문제를 풀었으므로, 먼저 투포인터로 접근을 한다.

• 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.
• 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

를 감안하면 시간초과가 날 것을 우려해 두번째로는 DP로 접근한다.

시간초과 코드 (투포인터)

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] s = br.readLine().split(" ");
        int[] board = new int[n + 1];
        int m = Integer.parseInt(br.readLine());
        for(int i = 1; i <= n; i++) {
            board[i] = Integer.parseInt(s[i - 1]);
        }
        for(int i = 0; i < m; i++) {
            s = br.readLine().split(" ");
            int start = Integer.parseInt(s[0]);
            int end = Integer.parseInt(s[1]);

            int res = symmetric(start, end, board);
            System.out.println(res);
        }

    }
    static int symmetric(int s, int e, int[] board) {
        int left = s;
        int right = e;
        while(left <= right) {
            if(board[left] == board[right]) {
                left++;
                right--;
            } else {
                return 0;
            }
        }
        return 1;
    }
}

예상대로 시간초과가 뜬다. (그러니까 골드4문제지)
작은 값부터 팰린드롬을 판별하는 범위를 점차 확대하면서 DP 배열을 채워나가는 과정을 진행해야 한다.

1. i, j가 같을 경우 무조건 팰린드롬이므로 dp[i][j] = 1을 삽입한다.
2. arr[i - 1] == arr[i] 일 경우에도 팰린드롬이므로 dp[i - 1][i] = 1을 삽입한다.

여기서 i는 팰린드롬의 길이를 나타내고, j는 시작 인덱스를 나타낸다.

코드 (DP)

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] s = br.readLine().split(" ");
        int[] board = new int[n + 1];
        int[][] dp = new int[n + 1][n + 1];
        int m = Integer.parseInt(br.readLine());

        for(int i = 1; i <= n; i++) {
            board[i] = Integer.parseInt(s[i - 1]);
            dp[i][i] = 1; // 같은 행, 열은 1로 초기화
            
            if(board[i - 1] == board[i]) {
            	dp[i - 1][i] = 1; // 붙어있는 인덱스끼리도 값이 같으면 1로 초기화
            }
        }

        for(int i = 2; i < n; i++) {
            for(int j = 1; j <= n - i; j++) {
                if(board[j] == board[j + i] && dp[j + 1][j + i - 1] == 1) {
                    dp[j][j + i] = 1;
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; i++) {
            s = br.readLine().split(" ");
            int start = Integer.parseInt(s[0]);
            int end = Integer.parseInt(s[1]);


            sb.append(String.valueOf(dp[start][end]) + "\n");
        }
        System.out.println(sb.toString());
    }
}

i = 2 부터 진행한다. 어차피 i = 1일 경우와 행열이 같은 경우는 위에서 이미 초기화했기 때문이다.
j <= n - i는 j가 시작 인덱스고 i값에 따라 끝 인덱스가 정해지므로 java.lang.ArrayIndexOutOfBoundsException 에러를 방지하기 위해 범위를 조정하였다.
board[j] == board[j + i]는 시작과 끝이 같은지를 확인하는 조건이고, dp[j + 1][j + i - 1] == 1는 S, E사이의 배열이 팰린드롬인지 확인하는 조건이다.

실제로 dp배열을 출력해보면 다음과 같다. (메모제이션을 통해 빨간 네모박스의 값이 팰린드롬임을 체크)

i = 2부터 확장해나가면서 S, E의 팰린드롬 여부를 메모제이션을 통해 전체 배열의 팰린드롬 여부를 기록하고, 질문에 따라 바로 출력하면 시간초과를 피할 수 있다.

시간 복잡도: O(N*M) -> O(N^2)