[🥇3 / 백준 10942 / 파이썬 ] 팰린드롬?

 

10942번: 팰린드롬?

문제

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

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

 

예제 입력  7 1 2 1 3 1 2 1 4 1 3 2 5 3 3 5 7

예제 출력  1 0 1 1

 

풀이

 

팰린드롬 수를 판별하는 문제이다.

 

수열의 크기가 최대 2,000이고 질문의 개수가 최대 1,000,000으로 매우 많기 때문에,

단순히 문자열을 계속하여 뒤집어 확인하는 O(m*n)의 시간복잡도로는 통과할 수 없다.

 

다이나믹 프로그래밍을 적용하기 위해 이 문제를 어떻게 부분 문제로 풀 수 있는지 생각해 보자.

 

 

1 2 1 3 1 2 1 예제의 팰린드롬 수이다.

자세히 보면, 당연하게도 수를 뒤집어도 같아야 하기 때문에 가운데를 기준으로 대칭을 이루고 있는 것을 알 수 있다.

 

여기서, 만약 1 3 1 을 이미 팰린드롬 수로 구했다고 가정해 보자.

1 2 1 3 1 2 1 을 팰린드롬 수로 판별하고 싶다면, 맨 처음 지점과 끝 지점을 비교하면서

점점 가운데로 좁혀 오는 방식으로 검사한다.

 

1 2 1 3 1 2 1  양측의 수가 같으므로 다음으로 넘어간다.

1 2 1 3 1 2 1  마찬가지이다. 다음으로 넘어간다.

1 2 1 3 1 2 1  이미 구했던 팰린드롬 구간이다! 더 이상 검사할 필요 없이 전체 수는 팰린드롬 수로 판별된다.

 

팰린드롬 수로 판별되었으므로 1을 출력하고,

다음 검사에도 사용하기 위해 dp배열에 해당 구간을 메모이제이션 해준다.

 

만약 검사를 진행하던 중 양쪽의 숫자가 다르다면,

팰린드롬 숫자가 아니므로 0을 출력하고 반복을 탈출한다.

 

 

문제의 특성 상 print가 매우 많아지기 때문에

배열에 저장하고 한 번에 출력하는 방식으로 코드를 작성했다.

 

import sys
input = sys.stdin.readline

n = int(input())
p = list(map(int,input().split()))
dp = [[0 for i in range(n)] for i in range(n)]
r = []

for i in range(int(input())):
    start, end = map(int,input().split())
    start -= 1; end -=1
    
    # 1글자면 무조건 팰린드롬.
    if start == end:
        r.append(1)
        dp[start][end] = 1
        continue
    
    # 2글자일 경우 각각 같은 숫자면 통과.
    # 아래 코드가 없어도 통과되지만, 미약하게 시간복잡도가 향상된다.
    if end - start == 1 and p[start] == p[end]:
        r.append(1)
        dp[start][end] = 1
        continue
    
    # 이미 팰린드롬으로 판별한 경우 팰린드롬 처리
    if dp[start][end] != 0:
        r.append(1)
        continue
        
    # 한 글자씩 대조하며 비교. 
    # 중간에 팰린드롬 구간이 나올 경우 팰린드롬 처리
    i,j = start,end
    while(i<j):
        if p[i] == p[j]:
            if dp[i][j] == 1:
                r.append(1)
                dp[start][end] = 1
                break
            i +=1; j-=1
        else:
            r.append(0)
            break
    else:
        dp[start][end] = 1
        r.append(1)

for i in r:
    print(i)