[BOJ] 백준 10942 : 팰린드롬? (java)

🧪 10942 팰린드롬?

---

난이도 : 🌟 골드 4
유형 : 동적 프로그래밍

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

 

 

입력

 

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

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

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

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

 

출력

 

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

 

🧐 핵심 로직 

---

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

 

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

 

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

 

dp는 메모이제이션을 위해 사용되며 num[S] == num[E]이 true이면 dp[S][E]에 값을 저장함으로써 한 번 탐색한 것은 두 번

또 시키지않게 탐색 시간을 줄여준다.

 

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

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

 

💻 최종 코드 (892 ms)

---

import java.lang.reflect.Array;
import java.util.*;
import java.io.*;

public class Main {

    static int n, m;
    static int[] palindromes;
    static int[][] dp;
    public static void main(String[] args) throws Exception {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        n = Integer.parseInt(br.readLine());
        palindromes = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            palindromes[i] = Integer.parseInt(st.nextToken());
        }

        m = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()) - 1;
            int e = Integer.parseInt(st.nextToken()) - 1;

            boolean flag = checkPalindrome(s, e) == 1;

            if (flag) {
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }
        }

        System.out.println(sb);

        br.close();
    }

    private static int checkPalindrome(int s, int e) {

        if (s >= e) return 1;

        if (dp[s][e] != -1) return dp[s][e];

        if (palindromes[s] == palindromes[e]) return dp[s][e] = checkPalindrome(s + 1, e - 1);

        return 0;
    }
}

💻 반복문 코드 (788 ms)

---

import java.lang.reflect.Array;
import java.util.*;
import java.io.*;

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;
				}
			}
		}
		
	}
}