백준 10942번: 팰린드롬? (JAVA)

https://www.acmicpc.net/problem/10942

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을 출력한다.

 

---

 

풀이 1: 그냥 풀기

이 문제의 분류가 DP로 되어있지만, DP 풀이 생각이 잘 안나서 그냥 풀었습니다. evens, odds라는 int 배열을 만들어서, 각 index에서 시작하는 홀수 길이 팰린드롬 / 짝수 길이 팰린드롬의 최대 길이를 구했습니다. 이후 S, E를 적당히 처리해서 정답이 나오도록 하면 됩니다. 개인적으로는 이 풀이가 더 쉽다고 느껴졌습니다('골드 dp 푸는 사람이 팰린드롬 누가 못 구하냐?').

 

코드

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

public class Baekjoon10942_팰린드롬물음표 {

    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[] nums = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int[] odds = new int[N+1], evens = new int[N+1];
        for (int i = 1; i <= N; i++) {
            int j = 0;
            while (i-j > 0 && i+j <= N) {
                if (nums[i-j] == nums[i+j]) odds[i] = 1 + 2*j;
                else break;
                j++;
            }
        }

        for (int i = 1; i <= N; i++) {
            int j = 0;
            while (i-j > 0 && i+j+1 <= N) {
                if (nums[i-j] == nums[i+j+1]) evens[i] = 2 + 2*j;
                else break;
                j++;
            }
        }


        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            int l = (E-S)+1;
            if (l % 2 == 1) {
                sb.append(odds[(E+S)/2] >= l? 1+"\n": 0+"\n");
            } else {
                sb.append(evens[(E+S)/2] >= l? 1+"\n": 0+"\n");
            }
        }
        System.out.println(sb);
    }

}

 

 

풀이 2: DP 

'행렬 곱셈 순서'(https://www.acmicpc.net/problem/11049)로 대표되는 구간 DP로 문제를 해결할 수 있습니다.

boolean[][] dp를 선언한 후, dp[S][E]: "문자열 Str의 S부터 E까지가 팰린드롬인가?"를 구하면 됩니다.

구간 간격 j에 대해서 loop를 돌고, 그 안에서 시작 위치 i에 대해 loop를 돌립니다.

dp[i][i+j] = dp[i+1][i+j-1] AND Str[i] == Str[j]임을 알 수 있습니다. 식을 보면 알겠지만, i+1 <= i+j-1 이 보장되지 않으므로 구간 간격 j가 1보다 작거나 같은 경우에 대해서는 따로 처리를 합니다.

 

코드

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

public class Baekjoon10942_팰린드롬물음표DP {

	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[] nums = new int[N+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		boolean[][] dp = new boolean[N+1][N+1]; // 
		for (int j = 0; j < N; j++) { // j <= 1 실행 횟수를 N^2번에서 N번으로 줄이기
			if (j <= 1) {
				for (int i = 1; i <= N - j; i++) {
					dp[i][i+j] = (nums[i] == nums[i+j]);
				}
			} else {
				for (int i = 1; i <= N - j; i++) {
					dp[i][i+j] = (nums[i] == nums[i+j] && dp[i+1][i+j-1]);
				}
			}
		}

		int M = Integer.parseInt(br.readLine());
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int S = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			sb.append(dp[S][E]? 1+"\n": 0+"\n");
		}
		System.out.println(sb);
	}

}