[알고리즘] 팰린드롬? (백준 10942번)

10942번: 팰린드롬?

 팰린드롬을 판별하는 동적 프로그래밍 + 문자열 처리 문제이다.

 우선 팰린드롬이란 문자열 중앙을 기준으로 좌측, 우측이 마치 데칼코마니처럼 일치하는 경우를 말한다.

EX) 121, 5, 2345432

 

 문제에선 S 인덱스부터 E 인덱스까지의 문자열이 팰린드롬인지를 판별하라고 했는데 동적 프로그래밍을 사용하지 않고 일일이 계산한다면 O(N ^ 3) 혹은 O (N * M) 의 시간이 걸리는데 최악의 경우 무려 80억번의 계산이 필요하다.

 하지만 동적 프로그래밍을 사용해서 구하게 된다면 O (N ^ 2) 의 시간, 즉 최악의 경우 4백만번 정도의 계산으로 모든 경우를 구할 수 있다. (시간 복잡도 계산을 잘 못하는데 아마 맞겠지?)

 

 

Solution

 우선 팰린드롬의 판별은 i 값 = j 값임과 동시에 (i+1, j-1)가 팰린드롬이라면 팰린드롬으로 판별하게 된다.

즉, '1 2 1'의 팰린드롬을 판별하면 (list[1] = 1) == (list[3] == 1) && isPalin[2][2] == true 이므로 1 2 1 은 팰린드롬이 맞다.

 이에 따라 팰린드롬 판별 순서는 k 인덱스 값 기준으로 좌측, 우측, 양측으로 판별하게 된다.

원본 리스트

k=1

k=2

isPalin[1][2]

isPalin[2][3]

isPalin[1][3]

 그림으로 표현하자면 대략 이렇다. k 기준으로 좌측끝까지 판별, 우측끝까지 판별, 양측으로는 어느쪽이든 list의 끝에 다다를 때까지 진행한다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {


	public static void main(String[] args) {

		try
		{
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

			int N = Integer.parseInt(br.readLine());

			int list[] = new int[N+1];

			boolean isPalin[][] = new boolean[N+1][N+1];

			StringTokenizer strtok = new StringTokenizer(br.readLine());

			for(int i = 1;i < list.length; i++)
				list[i] = Integer.parseInt(strtok.nextToken());

			for(int k = 1;k <= N;k++)
			{
				int i = 0;

				while(1 <= k - i || k + i <= N)
				{
					int index1 = k - i;
					int index2 = k + i;

					//k 기준으로 좌측
					if(1 <= index1)
					{
						if(k - index1 < 2)
						{
							if(list[index1] == list[k])
								isPalin[index1][k] = true;
						}
						else
						{
							if(list[index1] == list[k] && isPalin[index1+1][k-1])
								isPalin[index1][k] = true;
						}
					}

					//k 기준 우측
					if(index2 <= N)
					{
						if(index2 - k < 2)
						{
							if(list[k] == list[index2])
								isPalin[k][index2] = true;
						}
						else
						{
							if(list[k] == list[index2] && isPalin[k+1][index2-1])
								isPalin[k][index2] = true;
						}
					}

					//k 기준 양측
					if(1 <= index1 && index2 <= N)
					{
						if(index2 - index1 < 2)
						{
							if(list[index1] == list[index2])
								isPalin[index1][index2] = true;
						}
						else
						{
							if(list[index1] == list[index2] && isPalin[index1+1][index2-1])
								isPalin[index1][index2] = true;
						}
					}

					i++;
				}
			}

			int M = Integer.parseInt(br.readLine());

			for(int i = 0;i<M;i++)
			{
				strtok = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(strtok.nextToken());
				int b = Integer.parseInt(strtok.nextToken());

				if(isPalin[a][b])
					bw.write("1\n");
				else
					bw.write("0\n");
			}

			bw.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}

	}
}