[백준] 10942 - 팰린드롬? (JAVA)

[백준] 10942 - 팰린드롬?

사실 처음에는 주어진 질문 M번에 대해 일일이 팰린드롬인지 체크를 해주는 방식으로 풀었는데 그래도 통과는 할 수 있었다.
근데 풀면서도 이게 맞나?? 값을 저장해놓고 쓸 수 있을 것 같은데... DP??? 라는 생각이 들어서 다시 시도 해보았다.

역시 DP 점화식 세우기가 어려워서 애먹었지만 결과적으로 시간을 반 정도로 줄일 수 있었다.
나중의 나를 위해... 내가 푼 방법을 차례로 적어보겠다.

1. 우선 칠판에 적힌 수를 입력받을 int 배열 nums와 isPalindrome이라는 2차원 boolean 배열을 선언한다. isPalindrome의 행 인덱스를 문자열의 시작, 열 인덱스를 문자열의 끝으로 간주한다.
   

2. 칠판에 적힌 숫자를 입력받을 때 문자 하나는 무조건 팰린드롬이므로 시작 인덱스와 끝 인덱스가 같은 경우는 isPalindrome 값을 true로 넣어준다.
   또한 현재 주어진 문자와 nums[현재 인덱스-1]의 문자와 동일한 경우에도 길이가 2인 팰린드롬이므로 isPalindrome 값을 true로 넣어준다.
   

3. 길이가 1, 2인 경우는 체크했으므로 이제 길이가 3(간격이 2)인 경우부터 길이가 N (간격이 N-1)인 경우까지 차례로 체크해주면 된다.
   아래 이중 포문에서 i는 간격을 하나씩 늘려가는 반복문이고, j는 시작인덱스이다. 이렇게 for문을 돌면서 현재 체크하려는 부분의 양쪽 끝을 제외한 문자열이 팰린드롬인지 확인하고, 이것이 팰린드롬이라면 양쪽 끝의 문자가 서로 같은 값인지까지 체크해주면 된다.
   

아래가 전체 소스코드이다.

// 10942 - 팰린드롬?
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());

        int[] nums = new int[N+1];
        // 행 인덱스는 문자열의 시작, 열 인덱스는 문자열의 끝
        boolean[][] isPalindrome = new boolean[N + 1][N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N+1; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
            // 문자 하나는 무조건 팰린드롬
            isPalindrome[i][i] = true;
            // 이전 인덱스의 문자와 현재 문자가 동일한 경우에도 팰런드롬
            if(nums[i-1] == nums[i]) isPalindrome[i-1][i] = true;
        }
        for (int i = 2; i < N; i++) { // i는 간격
            for (int j = 1; j + i < N + 1; j++) { // i+j가 마지막 인덱스보다 작거나 같을 때까지만 반복 
                isPalindrome[j][j+i] = isPalindrome[j+1][j+i-1] && nums[j] == nums[j+i]; // 양쪽 끝을 제외한 문자열이 팰린드롬인지 && 양쪽 끝이 동일한 문자인지 체크
            }
        }
        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            bw.write(isPalindrome[start][end] ? "1\n" : "0\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }

// 처음에 사용했던 팰린드롬 체크 메서드
    static boolean checkItIsPalindrome(int start, int end, int[] nums) {
        boolean isPalindrome = true;
        for (int i = 0; i < (end-start+1)/2; i++) {
            if (nums[start+i] != nums[end - i]) {
                isPalindrome = false;
                break;
            }
        }
        return isPalindrome;
    }
}