10942 - 팰린드롬?

이 문제는 길이가 N인 어떤 수열이 주어졌을 때, [S, E]가 회문인지에 대한 M개의 질의에 대해 답해야 한다.

만약 이 문제를 단순히 하나의 질의마다 [S,E]까지가 회문인지 확인해 답변한다면, 최악의 경우 NM번의 계산을 할 것이고 그 결과 시간제한에 걸릴 것이다. 따라서 이것보다 효율적인 방법을 생각해 내야 한다.

여기서 회문의 성질을 생각해보자. 회문은 문자열의 중심을 기준으로 좌, 우가 대칭인 문자열이다. 즉 아래와 같은 형태이다.

1 2 3 4 5 4 3 2 1

이러한 성질을 이용하면 다음과 같은 점화식을 떠올릴 수 있다.

1. S == E, 즉 수열의 길이가 1이면 회문이다.
2. S + 1 == E, 즉 수열의 길이가 2이면 두 숫자가 같을 때 회문이다.
3. S + 1 < E, 즉 수열의 길이가 2보다 크면 [S+1, E-1]이 회문이면서 S번째 숫자와 E번째 숫자가 같을 때 회문이다.

그러나 또 하나의 고민은 점화식을 어떤 순서로 계산해야 하는가이다. 이를 탐구하기 위해 아래 표를 보자. 아래 표는 dp[s][e]를 계산할 때 참조해야 하는 이전 (s,e)를 작성해 놓은 표이다. 예를 들어 dp[2][5]를 알아내고 싶다면 dp[3][4]의 값을 참조해야 한다. 또한 x표시는 이전 dp값을 참조할 필요가 없다는 뜻이다. 수열의 길이가 1개이거나 2개이면 내부에 수열이 더 없기 때문이다.

S\E	1	2	3	4	5
1	x	x	(2,2)	(2,3)	(2,4)
2		x	x	(3,3)	(3,4)
3			x	x	(4,4)
4				x	x
5					x

위 표를 관찰해 보면 S=3 은 S=4를 참조하고, S=2는 S=3을 참조하는 것을 볼 수 있다. 한편 E 기준으로는 E=5일 때 E=4를 참조하고, E=3일 때 E=2를 참조한다. 그러므로 S 기준으로는 역행, E 기준으로는 순행으로 반복문을 돌면 된다. 즉 S는 5부터 1까지, E는 S부터 5까지 중첩 for문을 돌리면 된다.

🔗 문제 코드

코드

필요한 변수를 선언한다. dp는 점화식의 결과를 담을 배열이고, nums는 수열의 원소들을 담아놓을 배열이다.

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static boolean[][] dp;
    static int[] nums;

메인 메서드에서 n을 입력받은 뒤, nums 배열과 dp 배열을 메모리에 할당한다. 그런 다음 수열 정보를 입력받는다.

public static void main(String[] args) throws IOException {
    int n = Integer.parseInt(br.readLine());
    nums = new int[n+1];
    dp = new boolean[n+1][n+1];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= n; i++)
        nums[i] = Integer.parseInt(st.nextToken());

앞서 말했던 규칙에 따라 점화식을 계산한다. 먼저 문자열의 길이가 1인 경우 항상 회문으로 불 수 있으므로 먼저 dp[i][i] = true로 저장해 둔다. 그런 다음 i = n .. 1까지, j = i+1 .. n까지 반복하며 점화식을 계산한다.

점화식의 의미는 i+1 == j 이면 nums[i] == nums[j]를 계산하고, 그렇지 않으면 dp[i+1][j-1]과 nums[i] == nums[j]가 모두 참인지 확인하라는 의미이다.

    for (int i = 1; i <= n; i++) 
        dp[i][i] = true;

    for (int i = n; i >= 1; i--) {
        for (int j = i+1; j <= n; j++) {
            dp[i][j] = (i+1 == j || dp[i+1][j-1]) && (nums[i] == nums[j]);
        }
    }

마지막으로 m개의 질의를 입력받아 dp 배열을 통해 회문 여부를 판별한 뒤 그 결과를 출력한다.

    int m = Integer.parseInt(br.readLine());
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < m; i++) {
        st = new StringTokenizer(br.readLine());
        int s, e;

        s = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        sb.append(dp[s][e] ? 1 : 0).append("\n");

    }  
    System.out.print(sb);
}

전체 코드

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static boolean[][] dp;
    static int[] nums;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        nums = new int[n+1];
        dp = new boolean[n+1][n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++)
            nums[i] = Integer.parseInt(st.nextToken());


        for (int i = 1; i <= n; i++) 
            dp[i][i] = true;

        for (int i = n; i >= 1; i--) {
            for (int j = i+1; j <= n; j++) {
                dp[i][j] = (i+1 == j || dp[i+1][j-1]) && (nums[i] == nums[j]);
            }
        }

        int m = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s, e;

            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());

            sb.append(dp[s][e] ? 1 : 0).append("\n");

        }  
        System.out.print(sb);
    }
}

시간복잡도

dp 배열을 완성하는 데 $O(N^2)$, $M$개의 질의에 대한 결과를 출력하는 데 $O(M)$의 시간복잡도가 걸린다. 따라서 이 코드의 시간복잡도는 $O(N^2 + M)$이다.

$N \le 2,000$, $M \le 1,000,000$ 이므로 최악의 경우 $4,000,000 + 1,000,000 = 5,000,000$번, 즉 5백만번 연산하게 된다. 이는 0.5초 내 충분히 통과할 수 있는 연산 횟수이다.