📖 [백준알고리즘 풀이] Q.10942 팰린드롬? 문제 풀이 - java

📖 문제

https://www.acmicpc.net/problem/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개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

🔍 접근법

Q.10942 팰린드롬? 문제입니다.

자연수 N개가 주어지고

M번의 질문이 주어지는데

각 질문마다 S부터 E까지의 수가 팰린드롬인지를 확인하는 문제입니다.

처음에는 팰린드롬의 특성을 이용해

문자열의 substring을 이용해 S부터 E까지의 문자열을 만든후

reverse 함수를 이용해 풀이하였습니다.

하지만 주어진 질문의 개수 M이 너무 많아 시간초과가 났습니다.

그래서 다음은 동적 프로그래밍을 이용해 풀이할 수 있었습니다.

팰린드롬은 S부터 E까지의 수가 대칭이 되면 됩니다.

그러므로 S <-> E 사이의 숫자들이 팰린드롬이고 S번째 수 E번째 수가 같다면 팰린드롬입니다.

즉 S+1번째부터 E-1번째 수들이 팰린드롬이고 S번째 수 E번째 수가 같으면 됩니다.

if (dp[i+1][j-1] == 1 && numbers[i]==numbers[j]) true => 팰린드롬

위의 규칙을 이용하면 풀이가 가능합니다.

단, S와 E가 같은 경우에는 즉 길이가 1인 경우에는 무조건 팰린드롬이므로 먼저 팰린드롬임을 표시해주고

S부터 E의 길이가 2일 때는 S번째 수와 E번째 수가 같다면 팰린드롬임을 표시해줍니다.

그 이후

길이가 3인 경우부터 위의 규칙을 이용해

동적 프로그래밍 방식으로 풀이가 가능합니다.

💻 코드

1. String reverse를 이용한 풀이 (시간초과)

package problem.dynamic.Q10942;

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

public class Main_10942_1 {

    static String palindrome;
    static int n,m;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        input();
        System.out.println(sb.toString());
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        palindrome = br.readLine().replaceAll(" ","");
        m = Integer.parseInt(br.readLine());
        for(int i=0; i<m; i++){
            String temp[] = br.readLine().split(" ");
            int start = Integer.parseInt(temp[0]);
            int end = Integer.parseInt(temp[1]);

            if(end-start+1 == 2){
                sb.append(0);
                sb.append("\n");
                continue;
            }

            String subString = palindrome.substring(start-1,end);
            if (isPalindrome(subString) ){
                sb.append(1);
            }
            else
                sb.append(0);
            sb.append("\n");
        }
        br.close();
    }

    private static boolean isPalindrome(String str) {
        String reverseStr =  new StringBuilder(str).reverse().toString();
        if (str.equals(reverseStr))
            return true;
        else
            return false;
    }
}

2. 동적 프로그래밍을 이용한 풀이 (정답)

package problem.dynamic.Q10942;

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

public class Main_10942_2 {

    static int[] numbers;
    static int dp[][];
    static int n,m;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        input();
        System.out.println(sb.toString());
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        String palindrome[] = br.readLine().split(" ");
        numbers = new int[n+1];
        dp = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            numbers[i] = Integer.parseInt(palindrome[i-1]);
        }
        solve();
        m = Integer.parseInt(br.readLine());
        for(int i=0; i<m; i++){
            String temp[] = br.readLine().split(" ");
            int start = Integer.parseInt(temp[0]);
            int end = Integer.parseInt(temp[1]);
            sb.append(dp[start][end]+"\n");
        }
        br.close();
    }

    private static void solve() {
        for (int i = 1; i <= n; i++) {
            dp[i][i] = 1;
        }

        for (int i = 1; i <= n - 1; i++) {
            if (numbers[i] == numbers[i + 1]) {
                dp[i][i + 1] = 1;
            } else {
                dp[i][i + 1] = 0;
            }
        }


        for (int j = 3; j <= n; j++) {
            for (int i = 1; i <= j; i++) {
                if (dp[i][j] == 1 || j - i == 1) {
                    continue;
                }
                if (dp[i + 1][j - 1] == 1 && numbers[i] == numbers[j]) {
                    dp[i][j] = 1;
                }
            }
        }
    }
}

Written on April 2, 2021