[백준] 10942번 팰린드롬 문제 풀어보기 : Programming Story

1. 문제

1) 링크

www.acmicpc.net/problem/10942

2) 문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 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개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

3) 입력

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

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

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

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

4) 출력

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

2. 풀이

더 자세한 문제의 제한은 위 백준 링크에서 찾아볼 수 있다.

이 문제는 더 작은 문제를 재귀적으로 호출해나가면서 풀 수 있는 방법이다.

palindrome이란 앞에서부터 읽은 것과 뒤에서부터 읽은 것이 같은 문자열을 의미하는데,

i부터 j까지 palindrome인지를 확인하기 위해서는 먼저 i번째 문자와 j번째 문자가 같은지를 확인한 다음, i+1부터 j-1번째 문자열이 palindrome인지를 다시 재귀적으로 호출하면서 확인해주면 된다.

또한 palindrome의 특성상 길이가 1이라면 무조건 palindrome이 되고 만약 길이가 2라면 0번째 문자와 1번째 문자가 같은지를 확인해주게 된다. (이것이 재귀호출에 있어서 base case가 되는 것이라고 할 수 있다)

3. 코드

코드를 보면 아래와 같다.

import java.util.*;

public class Main{
     static int[] a;
    static int[][] d;
    static int palin(int i, int j){
        if (i==j) {
            return 1; //길이가 1이면 무조건 palindrome
        }
        else if (i+1==j){
            //길이가 2일 경우
            if (a[i]==a[j]){
                return 1;
            }
            else{
                return 0;
            }
        }
        if (d[i][j]!=-1){
            return d[i][j];
        }
        if (a[i]!=a[j]){//첫 값과 끝 값이 같지 않으면 무조건 palindrome이 아님
            d[i][j]=0;
            return 0;
        }else{
            d[i][j]=palin(i+1, j-1);
            return d[i][j];
        }
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        a = new int[n];
        d = new int[n][n];
         for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
            Arrays.fill(d[i],-1);
        }
        StringBuilder sb=new StringBuilder();
        int t=sc.nextInt();
        while(t-->0){
            int i=sc.nextInt();
            int j=sc.nextInt();
            sb.append(palin(i-1,j-1));
            sb.append('\n');
        }
        System.out.println(sb);
    }
}

palin 이라는 함수를 만들어서 재귀적으로 호출해주게 구현을 했다.

물론 일반적으로 palindrome을 구할 때는 이렇게 재귀적으로 푸는 방법이 흔한 방법은 아니지만 이 경우에는 여러 test case에 대해서 문제를 풀어주어야 하기 때문에 재귀적으로 구현해보았다.