백준 10942번_팰린드롬? (Python)

문제

시간제한: 0.5 초

 

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 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을 출력한다.

 

코드

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
S = list(map(int, input().split()))
queue = deque()

DP = [[0]*N for i in range(N)]

for i in range(N):
    DP[i][i] = 1
    queue.append((i, 1))
    if i>0 and S[i] == S[i-1]:
        DP[i][i-1] = DP[i-1][i] = 1
        queue.append((i-0.5, 1.5))

while len(queue):
    L = len(queue)
    for i in range(L):
        center, r = queue.popleft()
        leftend, rightend = int(center-r), int(center+r)
        if leftend>=0 and rightend<N:
            if S[leftend] == S[rightend]:
                DP[leftend][rightend] = DP[rightend][leftend] = 1
                queue.append((center, r+1))

for i in range(int(input())):
    s, e = map(int, input().split())
    print(DP[s-1][e-1])

 

해설

만약에 질문 각각에 대해서 매번 팰린드롬인지 확인한다면 연산이 20억회까지 가능하므로 최대한 줄여야 한다. 최고의 방법은 N이 2000 정도로 작기 때문에 $O(N^2)$로 배열에서 얻을 수 있는 모든 구간의 팰린드롬의 여부를 미리 알아내는 것이다. 하지만 이 경우에서 브루트포스를 돌리려면 최대 2000*2000/2개의 구간에 대해서 각각 팰린드롬을 검사해야 하니 오히려 더 비효율적이므로, 간단한 방법을 찾아야 한다.

 

원래는 2차원 DP 배열에서 다이나믹 프로그래밍을 돌리려고 했으나, 정작 이 배열은 DP의 정의처럼 앞의 결과를 이용해서 그다음 답을 구해내는게 아니라 각 구간의 팰린드롬의 여부를 저장하는 배열로 사용되었다. 알고리즘에도 다이나믹 프로그래밍을 사용한다고 되어 있지만, 나는 큐를 이용해서 문제를 풀었다.

 

발상은 다음과 같다. 만약에 어떤 팰린드롬이 있다면, 중심점이 있을 것이다. 팰린드롬의 길이가 홀수라면 중심점이 중간의 숫자가 될 것이고, 짝수라면 중간의 두 숫자 사이가 될 것이다. 그리고 어떤 구간이 팰린드롬이 되려면, 그 중심점을 다시 중심점으로 가지는 자신의 부분 구간들도 모조리 다 팰린드롬이 되어야 한다는 것이다. 즉, 이미 팰린드롬이라 확인된 구간들의 양쪽을 조금씩 같은 길이만큼 늘려서(즉, 중심점이 같도록 한다) 얻을 수 있는 구간 배열만을 검토해도 충분한 것이다.

 

우선 '가장 처음'에 팰린드롬으로 확인되는 구간들을 찾아야 한다. 간단하게 수 하나로 이루어진 구간은 모두 팰린드롬이고, 이외에도 길이 1에서 양쪽으로 확장하면 홀수 길이밖에 고려하지 못하므로 짝수 길이의 팰린드롬도 고려해주기 위해 인접한 두 수로 이루어진 팰린드롬 구간을 모두 찾으면 된다.

 

현재까지 발견한 팰린드롬을 (중심점의 좌표, 이 팰린드롬에서 한 칸 확장시킨 구간이 중심점에서 양쪽으로 뻗은 거리)의 형태로 큐에 저장해둔다. 이때 짝수 길이의 중심점은 중앙의 두 수의 평균을 구해준 뒤 뻗은 거리를 1.5와 같이 저장해준다. 그다음 이 둘을 큐에서 꺼내고 3, 4길이의 구간으로 확장한 후 팰린드롬만을 다시 큐에 넣고, 그다음 똑같이 5, 6길이, 7, 8길이의 팰린드롬...을 순서대로 찾아가면 대부분 팰린드롬 구간들만 걸려들어 검토하는 이상적에 가까운 시간복잡도의 코드를 만들 수 있다. 최악의 경우도 $O(N^2)$다.