[JAVA 알고리즘]BAEKJOON 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개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

제한사항

• 없음

입출력 예

input	return
7 1 2 1 3 1 2 1 4 1 3 2 5 3 3 5 7	1 0 1 1

---

문제 분석

팰린드롬이란 앞에서 읽어도 뒤에서 읽어도 동일한 형태의 숫자 혹은 문자열을 뜻한다.

팰린드롬이 성립할 수 있는 조건

• 홀수 일경우, 중간수를 제외한 숫자의 앞자리와 뒷자리가 같을 경우 성립이 된다.
• 짝수 일 경우, 숫자의 앞자리와 뒷자리가 같을 경우 성립이 된다.

맨앞과 맨뒤에서부터 하나씩 증가와 감소를 하면서 비교해 성립여부를 알 수 있다.

매번 테스트 케이스 마다 전부 반복을 하면 많은 경우의 수가 발생하기 때문에 처음 한 번에 팰린드롬이 성립여부를 배열에 저장을 하고 테스트 케이스에 맞게 성립 결과만 출력해 준다.

손으로 풀기

1. 수열을 배열에 입력한다.
2. 시작 숫자와 끝숫자를 범위로 구분을 하기 위해 이차원배열을 만든다.
3. 주어진 N의 크기만큼 반복해 해당 수열에서 나올 수 있는 범위들의 팰린드롬 성립을 확인한다.
   1. 끝 숫자는 시작 숫자보다 작을 수 없기 때문에 이전 크기부터 N의 만큼 반복한다.
   2. 시작 위치는 증가시키고 끝 위치는 감소시키면서 범위 내 시작 숫자와 끝 숫자가 전부 0일 경우, 참을 반환하고 아닐 경우 거짓을 반환한다.
4. 주어지는 테스트 케이스를 만들어둔 이차원배열의 인덱스를 통해 참, 거짓을 출력한다.

나의 문제풀이

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

public class Main {

    static int[] sequence;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        // 수열의 크기
        int N = Integer.parseInt(bufferedReader.readLine());

        // 수열 입력
        sequence = new int[N];
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            sequence[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        boolean[][] dp = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                dp[i][j] = isPalindrome(i, j);
            }
        }

        // 질문의 개수
        int M = Integer.parseInt(bufferedReader.readLine());

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < M; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            // 수열의 개수
            int S = Integer.parseInt(stringTokenizer.nextToken());
            // 목표 합계
            int E = Integer.parseInt(stringTokenizer.nextToken());

            if (dp[S - 1][E - 1]) {
                stringBuilder.append(1).append("\n");
            } else {
                stringBuilder.append(0).append("\n");
            }
        }

        System.out.println(stringBuilder);
    }

    private static boolean isPalindrome(int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (sequence[i] - sequence[j] != 0) {
                return false;
            }
        }
        return true;
    }
}

표를 그리면서 반복되는 형태를 찾아내어 규칙을 바탕으로 dp를 구성했는데, 해당 형태는 반복구조를 dp로 이용한 게 아니라 미리 모든 경우의 수를 만들어두고 가저온 방식으로 다이나믹 프로그래밍이라기에는 아쉬운 부분이 있었다. 주어진 수열의 크기가 적어 성립된 느낌이다. 규칙에서 홀수, 짝수가 아닌 다른 조건을 찾아봤을 때, 숫자의 자리 수로 조건을 하면 좀더 다이나믹 프로그래밍의 규칙이 보일 수 있었다.

수정 조건

• 숫자가 한자리 일경우, 자기 자신뿐이니 성립이 된다.
• 숫자가 두 자리 일경우, 두 수가 같으면 성립이 된다.
• 숫자가 세 자리 이상일 경우, 양 끝의 수가 동일할 때 범위가 이전 범위가 성립했으면 성립이 된다.
  • 이전 범위 : 다음 시작 숫자와 이전 끝 숫자의 범위 (시작 +1, 끝 -1)
  • 양 끝 수를 제외한 중앙의 범위를 가지고 생각하면 된다.
• 조건을 확인하는 순서를 한자리 -> 두 자리 -> 세 자리 식으로 시작 기준에서 범위를 늘려가면서 반복하게 되면 다이나믹 프로그래밍 알고리즘을 사용할 수 있다.

private static void isPalindrome() {
		for (int i = 0; i < N - 1; i++) {
            dp[i][i] = true;
            dp[i][i + 1] = (sequence[i] == sequence[i + 1]);
        }
        for (int i = 2; i < N; i++) {
            for (int j = 0; j < N - 1; j++) {
                int k = j + i;
                dp[j][k] = (sequence[j] == sequence[k]) && dp[j + 1][k - 1];
            }
        }
    }

---

알고리즘 분류

• 다이나믹 프로그래밍

문제 출처 - https://www.acmicpc.net/problem/10942