[BOJ] 백준 10942번 펠린드롬? (Java)

• #10942 펠린드롬?
• 문제 풀이 
• 재귀함수 DP 풀이 
• 반복문 DP 풀이 

#10942 펠린드롬?

난이도 : 골드 3

유형 : DP / 문자열

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

 

 

 

문제 풀이 

펠린드롬(Palindrome; 회문)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열을 뜻한다.

예시) 'abcba'는 거꾸로 읽어도 'abcba'이기 때문에 펠린드롬이다. 

         'abcab'는 거꾸로 읽으면 'bacba'로 서로 다르기 때문에 펠린드롬이 아니다.

 

📚 조건

 ∙ 수열의 크기 N (1 <= N <= 2,000)

 ∙ 수열에 들어간 숫자 num (1 <= num <= 100,000 )

 ∙ 질문의 개수 M  (1 <= M <= 1,000,000)

 

일단 보기에는 문제 자체는 되게 간단해보이는데 시간제한이 걸려있다. 그래서 무작정 질문(최대 100만개)를 모두 계산하지 않도록 DP배열을 활용하여 메모이제이션을 해야한다.

 

풀이과정

수열이 담긴 배열을 num[] 이라고 하면 팰린드롬 탐색과정은 다음과 같다.

 

   1) 수열의 인덱스 중 S와 E에서 탐색을 시작한다.

   2) num[S] == num[E]이 true이면 , S+1, E-1의 탐색을 시작한다.

   3) (E-S+1)이 홀수인 경우 S==E, 짝수인 경우 S>E가 되면 탐색 종료한다.

 

여기서, 메모이제이션은 2번과정에 추가해주면 된다.

num[S] == num[E]이 true이면 dp[S][E]에 값을 저장함으로써 한 번 탐색한 것은 두 번 또 시키지않게 탐색 시간을 줄여준다.

 

이를 이제 코드로 구현하면 되는데 여기서 또 방법이 두가지있다.

 

첫 번째, 재귀함수를 사용하여 구현하기

두 번째, 반복문을 사용하여 구현하기

 

 

 

재귀함수 DP 풀이 

재귀함수는 스택을 사용하기 때문에 성능이 반복문보다 좋지는 않지만 구현하기 쉽다는 장점이 있다.

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

public class Main {

	static int[] num;
	static int[][] 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());
		num = new int[n+1];
		dp = new int[n+1][n+1];
		for(int i=0; i< n+1; i++) {
			Arrays.fill(dp[i], -1);
		}
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1; i<n+1; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		
		int t = Integer.parseInt(br.readLine());
		for(int i=0; i<t; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
            
			boolean flag = checkPalin(start, end) == 1? true : false;
			if(flag) {
				sb.append("1\n");
			}else {
				sb.append("0\n");
			}
		}
		
		System.out.println(sb.toString());
	}

	static int checkPalin(int s, int e) {
		if( s >= e) return 1;
		
		if(dp[s][e] != -1) return dp[s][e];
		
		if(num[s]==num[e]) {
			return dp[s][e] = checkPalin(s+1, e-1);
		}
		return 0;
	
	}
}

 

반복문 DP 풀이 

재귀함수 방식이 편하지만 연습을 위해 반복문으로도 풀어보았다.

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

public class Main {

	static int[] num;
	static boolean[][] dp;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
	
		num = new int[n+1];
		dp = new boolean[n+1][n+1];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1; i<n+1; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		for(int i = 1; i <= n; i++){
			dp[i][i] = true;
		}
		
		for(int i=1; i<=n-1; i++) {
			if(num[i] == num[i+1]) dp[i][i+1] =true;
		}
		checkPalin(n);
		
		int t = Integer.parseInt(br.readLine());
		for(int i=0; i<t; i++) {
		 st = new StringTokenizer(br.readLine());
		 int start = Integer.parseInt(st.nextToken());
		 int end = Integer.parseInt(st.nextToken());
		 
		 if(dp[start][end]) {
			sb.append("1\n");
		 }
		 else {
			 sb.append("0\n");
		 }
		}
		 
		 System.out.println(sb);
	}
	
	static void checkPalin(int n) {
	
		for(int i=2; i<n; i++) {
			for(int j=1; j<=n-i; j++) {
				if(num[j] == num[j+i] && dp[j+1][j+i-1]) {
					dp[j][j+i] = true;
				}
			}
		}
		
	}
}

 

 

 실행결과 비교

재귀함수 풀이

 

반복문 풀이

메모리는 역시 반복문이 더 효율성이 좋았지만 실행시간도 이론상으로는 반복문 풀이가 더 빨라야하는데... 이상하게 실행시간은 그닥 큰 차이가 없었다.