[BOJ] 10942번 - 팰린드롬? (Java)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

팰린드롬이란?

거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등

즉, 앞뒤로 읽어도 똑같다! (ex. 토마토)

[위키] https://ko.wikipedia.org/wiki/%ED%9A%8C%EB%AC%B8

 

이는 3가지 경우로 나누어 볼 수 있다.

• 길이가 1인 경우
  • 1, 2, 3, a, b, c
  • 무조건 팰린드롬이다.
• 길이가 2인 경우
  • 11, 22, 33, aa, bb, cc
  • 두 문자가 같을 경우에만 팰린드롬이다.
• 길이가 3이상인 경우
  • 121, aba
  • 맨 앞의 문자와 맨 끝의 문자가 같고 중간의 문자열이 팰린드롬일 경우에만 팰린드롬이다.

 

위의 성질을 이용해서 문자열에서 어느 부분이 팰린드롬인지 알아낼 수 있다.

n x n의 2차원 배열을 생성하여 dp[i][j]는 i번째 인덱스부터 j번째 인덱스의 문자열이 회문인지 아닌지를 저장해둔다.

 

이 성질을 이용하여 비슷한 문제를 풀었던 기억이 나서 적어본다.

[BOJ] 17609번 - 회문 (Java)

---

🍀 풀이 🍀

package Baekjoon;

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

public class DP10942 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int[] nums = new int[n];
        boolean[][] dp = new boolean[n][n]; //i-j까지의 수열이 팰린드롬이면 dp[i][j] = true
        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
            dp[i][i] = true; //길이가 1이면 무조건 팰린드롬
        }

        for(int i = 1; i < n; i++) { //길이가 2이면 두 수가 같아햐지만 팰린드롬
            if(nums[i-1] == nums[i]){
                dp[i-1][i] = true;
            }
        }

        //길이가 3이상인 수열인 경우
        for(int i = 2; i < n; i++) { //i = 수열 길이
            for(int j = 0; j < n-i; j++) { //j = 시작 인덱스
                if(nums[j] == nums[j+i] && dp[j+1][j+i-1]) dp[j][j+i] = true;
            }
        }

        int m = Integer.parseInt(br.readLine());
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            if(dp[start][end]) bw.write(1+"\n");
            else bw.write(0+"\n");
        }
        bw.flush();
        bw.close();
    }
}