10942번 - 팰린드롬?(dp, br, st)

문제:

 

풀이:

먼저, 팰린드롬이 뭔지 알아야한다.

(1, 2, 1), (a, b, c, b, a), (가, 나, 다, 나, 가) 등 대칭되는 문자들의 모음을 팰린드롬이라고 한다.

문제에서 알려주지않아 햇갈릴 수도 있지만, (1, 1), (1, 2, 2, 1)도 팰린드롬이며, 문자의 수가 짝수든 홀수든 상관 없다.

 

자 그럼 문제에서 준 보기를 이용해 문제를 풀어보자.

1

2

1

3

1

2

1

이렇게 배열이 주어졌다.

먼저 보기에서 설명하듯 숫자가 1개 있을 때는 모두 팰린드롬이다.

	1(1)		2(2)		3(1)		4(3)		5(1)		6(2)		7(1)
길이: 1	1	1	2	2	1	1	3	3	1	1	2	2	1	1
팰린드롬?	p		p		p		p		p		p		p

숫자가 두개 있을 때는 앞 뒤만 비교하고 같은 수라면 팰린드롬이다.

	1(1)		2(2)		3(1)		4(3)		5(1)		6(2)		7(1)
길이: 1	1	1	2	2	1	1	3	3	1	1	2	2	1	1
팰린드롬?	p		p		p		p		p		p		p

길이: 2	1	2	2	1	1	3	3	1	1	2	2	1
팰린드롬?	x		x		x		x		x		x		x

그럼 숫자 3개일 때는 어떨까?
당연하게도 맨앞, 뒤 숫자만 비교해주면 될 것이다.

	1(1)		2(2)		3(1)		4(3)		5(1)		6(2)		7(1)
길이: 1	1	1	2	2	1	1	3	3	1	1	2	2	1	1
팰린드롬?	p		p		p		p		p		p		p

길이: 2	1	2	2	1	1	3	3	1	1	2	2	1
팰린드롬?	x		x		x		x		x		x		x

길이: 3	1	1	2	3	1	1	3	2	1	1
팰린드롬?	p		x		p		x		p		x		x

 

길이가 4일때는 어떨까? 앞에 2개 뒤에 2개를 비교해야 할까?
그런식으로 하다간, 비교 해야할 수열이 많을때, 너무나 많은 계산을 해야할 것이다.

길이가 4인 수열이 팰린드롬인지 알려면, (1, 4) (2, 3)이 같은지 비교해야 한다.

만약 가운데 (2, 3)을 비교한 기록이 있고, 팰린드롬이라면 (1, 4)만 비교해서 같은지 알아보면 된다.

 

위같은 식으로 길이 4인 배열이 팰린드롬이기 알기 위해서는 길이 2인 수열이 팰린드롬인지 미리 알고 있다면 더 편하다.

다행히도 우리는 길이 2일때 비교해놓은 기록이 있다.

	1(1)		2(2)		3(1)		4(3)		5(1)		6(2)		7(1)
길이: 2	1	2	2	1	1	3	3	1	1	2	2	1
팰린드롬?	x		x		x		x		x		x		x

 

어떤 수열도 팰린드롬이 아니다 고로 길이 4인 배열은 팰린드롬이 될 수 없다.

	1(1)		2(2)		3(1)		4(3)		5(1)		6(2)		7(1)
길이: 1	1	1	2	2	1	1	3	3	1	1	2	2	1	1
팰린드롬?	p		p		p		p		p		p		p

길이: 2	1	2	2	1	1	3	3	1	1	2	2	1
팰린드롬?	x		x		x		x		x		x		x

길이: 3	1	1	2	3	1	1	3	2	1	1
팰린드롬?	p		x		p		x		p		x		x

길이: 4	1	3	2	1	1	2	3	1
팰린드롬?	x		x		x		x		x		x		x

 

수열의 길이가 5일때도 비슷한 방법으로 진행하면 된다.

바로 수열의 길이가 3인 배열이 팰린드롬이었는지 확인하는 것이다.

	1(1)		2(2)		3(1)		4(3)		5(1)		6(2)		7(1)
길이: 3	1	1	2	3	1	1	3	2	1	1
팰린드롬?	p		x		p		x		p		x		x

여기서 길이 5 배열 사이에 들어갈 수 있는 수열은 3 ~ 5(1,3,1)이다.

이렇게 길이 3이며 팰린드롬인 수열이 포함된 길이 5의 수열 앞, 뒤를 비교하면 아래와 같은 표가 완성된다.

	1(1)		2(2)		3(1)		4(3)		5(1)		6(2)		7(1)
길이: 1	1	1	2	2	1	1	3	3	1	1	2	2	1	1
팰린드롬?	p		p		p		p		p		p		p

길이: 2	1	2	2	1	1	3	3	1	1	2	2	1
팰린드롬?	x		x		x		x		x		x		x

길이: 3	1	1	2	3	1	1	3	2	1	1
팰린드롬?	p		x		p		x		p		x		x

길이: 4	1	3	2	1	1	2	3	1
팰린드롬?	x		x		x		x		x		x		x

길이: 5

2

2

팰린드롬?

x

p

x

x

x

x

x

길이 6 수열은 길이 4 수열 중 팰린드롬 수열이 없으므로 모두 팰린드롬이 아니다.

길이 7 수열은 1~7번째 숫자가 모두 포함된 수열 하나만 고려하면 된다.

그렇다면 이때 고려할 사항은

1. 2~6번째 숫자가 포함된 수열이 팰린드롬인지
2. 1번째 숫자와 7번째 숫자가 동일한지

1번째 사항은 이미 구해놓았고, 2~6번째 숫자가 포함된 수열은 팰린드롬 수열이 맞다.

2번째 사항은 1과 1이므로 2번째 사항도 맞다.

고로 아래와 같이 표가 완성된다.

	1(1)		2(2)		3(1)		4(3)		5(1)		6(2)		7(1)
길이: 1	1	1	2	2	1	1	3	3	1	1	2	2	1	1
팰린드롬?	p		p		p		p		p		p		p

길이: 2	1	2	2	1	1	3	3	1	1	2	2	1
팰린드롬?	x		x		x		x		x		x		x

길이: 3	1	1	2	3	1	1	3	2	1	1
팰린드롬?	p		x		p		x		p		x		x

길이: 4	1	3	2	1	1	2	3	1
팰린드롬?	x		x		x		x		x		x		x

길이: 5

2

2

팰린드롬?

x

p

x

x

x

x

x

길이: 6

팰린드롬?

x

x

x

x

x

x

x

길이: 5

1

1

팰린드롬?

p

x

x

x

x

x

x

위의 결과를 각각 dp 배열에 저장할 수 있을 것이다.

 

또한 위의 표를 구하며 알 수 있던 사실은, 길이가 3 이상인 어떤 수열이 팰린드롬 수열인지 알기 위해

해당 수열보다 앞 뒤로 한칸씩 짧은 수열이 팰린드롬 수열인지 알고 있으면, 팰린드롬 판정이 더 쉽다는 점이다.

 

이를 활용하여 아래와 같은 코드를 작성했다.

static void palindrome(int N, int[] arr, int[][] dp) {
    for (int i = 1; i <= N; i++) { // 길이가 1일때
        dp[i][i] = 1;
    }

    for (int i = 1; i < N; i++) { // 길이가 2일때
        if (arr[i] == arr[i + 1]) {
            dp[i][i + 1] = 1;
        }
    }

    for (int i = 2; i < N; i++) { // 길이가 3 이상일 때
        for (int j = 1; j + i<= N; j++) {
            if (dp[j+1][j+i-1] == 1) { // (2, 5)가 팰린드롬이려면, (3, 4)는 무조건 팰린드롬 이여야 함
                if (arr[j] == arr[j+i]) { // (3, 4)가 팰린드롬이라면, (2) 와 (5)만 비교하면 됨
                    dp[j][j+i] = 1;
                }
            }
        }
    }
}

길이가 1일때, 2일때, 3이상일 때로 나눠서 dp 배열을 완성했다.

길이가 2 이하인 배열은 앞 뒤로 한칸씩 짧은 수열이 없기 때문이다.

 

전체코드:

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[N + 1][N + 1];
        palindrome(N, arr, dp);

        int M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            sb.append(dp[start][end]).append("\n");
        }
        System.out.print(sb.toString());
    }

    static void palindrome(int N, int[] arr, int[][] dp) {
        for (int i = 1; i <= N; i++) { // 길이가 1일때
            dp[i][i] = 1;
        }

        for (int i = 1; i < N; i++) { // 길이가 2일때
            if (arr[i] == arr[i + 1]) {
                dp[i][i + 1] = 1;
            }
        }

        for (int i = 2; i < N; i++) { // 길이가 3 이상일 때
            for (int j = 1; j + i<= N; j++) {
                if (dp[j+1][j+i-1] == 1) { // (2, 5)가 팰린드롬이려면, (3, 4)는 무조건 팰린드롬 이여야 함
                    if (arr[j] == arr[j+i]) { // (3, 4)가 팰린드롬이라면, (2) 와 (5)만 비교하면 됨
                        dp[j][j+i] = 1;
                    }
                }
            }
        }
    }
}

 

시행착오:

총 2가지 시행착오를 겪었다.

1. 팰린드롬 수열이 홀수여야 가능하다고 생각함.
   나의 무식과 문제의 불친절함이 만든 문제였다고 생각한다.
   위의 결과 아래와 같은 코드가 만들어지게 되었다.
   그래도 문제에 대한 접근 방식이 크게 잘못된게 아니라 다행이었다.
   

   import java.util.Scanner;
   
   public class Main {
       public static void main(String[] args) {
           Scanner sc = new Scanner(System.in);
           int N = sc.nextInt();
           int[] arr = new int[N+1];
   
           for (int i = 1; i <= N; i++) {
               arr[i] = sc.nextInt();
           }
   
           int dp[][] = new int[N+1][N+1];
           for (int i = 1; i <= N; i++) {
               dp[i][i] = 1;
           }
           palindrome(N, arr, dp);
   
           int M = sc.nextInt();
           for (int i = 0; i < M; i++) {
               int start = sc.nextInt();
               int end = sc.nextInt();
               System.out.println(dp[start][end]);
           }
   
       }
   
       static void palindrome(int N, int[] arr, int[][] dp) {
           for (int i = 2; i < N; i+=2) {
               for (int j = 1; j + i<= N; j++) {
                   if (dp[j+1][j+i-1] == 1) {
                       if (arr[j] == arr[j+i]) {
                           dp[j][j+i] = 1;
                       }
                   }
               }
           }
       }
   }

2. 습관적 Scanner 사용
   분명 수많은 수를 입력받고, 출력해야 하는 상황이였는데,
   나의 게으름 때문에 습관적으로 Scanner을 사용하고 말았다.
   이렇게 많은 수를 입출력하는데에는 bufferedReader와 StringTokenizer을 사용해야 빠르다.
   일부로라도 Scanner을 당분간 사용하지 말아야겠다.
   ↓이유
   

   1. BufferedReader가 입력을 빠르게 처리하는 이유

   BufferedReader는 **입력 스트림을 버퍼(buffer)**를 사용해 읽기 때문에, 많은 양의 데이터를 처리할 때 매우 효율적입니다. 일반적인 Scanner는 입력을 한 글자씩 읽고 처리하는 반면, BufferedReader는 미리 데이터를 버퍼에 담아 한 번에 여러 글자를 처리하므로 속도가 훨씬 빠릅니다.

   • Scanner는 사용하기 편리하지만, 많은 데이터를 처리할 때 성능이 상대적으로 느립니다. 매번 입력할 때마다 파싱(parse)과 검사를 수행하기 때문입니다.
   • BufferedReader는 입력을 버퍼링하여 메모리에서 대량으로 읽고, 필요한 만큼만 처리할 수 있습니다. 따라서, 대량의 데이터를 반복해서 읽어들이는 상황에서 특히 유리합니다.

   2. StringTokenizer가 빠른 이유

   StringTokenizer는 문자열을 특정 구분자를 기준으로 나누는 작업에 특화된 클래스입니다. 이는 입력된 문자열을 빠르게 나누어 토큰화하는 역할을 합니다. 입력받은 데이터를 처리하는 과정에서 split() 메서드 대신 StringTokenizer를 사용하면 성능이 더 빠릅니다.

   • split() 메서드: 정규 표현식을 사용하므로 더 강력한 기능을 제공하지만, 정규식 처리가 추가되어 오버헤드가 큽니다.
   • StringTokenizer: 간단하게 공백, 쉼표 등의 구분자를 기준으로 문자열을 빠르게 분리하는 데 최적화되어 있기 때문에, 대량의 데이터를 처리하는 상황에서 더 효율적입니다.

   요약:

   • BufferedReader는 입력을 버퍼에 담아 한 번에 많은 양의 데이터를 처리할 수 있어, 대량의 데이터를 빠르게 입력받을 때 유리합니다.
   • StringTokenizer는 구분자를 기준으로 문자열을 빠르게 토큰화할 수 있어, 많은 양의 데이터를 효율적으로 분리하고 처리하는 데 적합합니다.