[BOJ] 10942 팰린드롬? (Python3)

문제

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

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

정답 코드

import sys

n = int(input())
nums = list(map(int, input().split()))
m = int(input())
dp = [[0 for i in range(n + 1)] for i in range(n + 1)]

for i in range(n):
    dp[i][i] = 1
    
for i in range(n - 1):
    if nums[i] == nums[i + 1]:
        dp[i][i + 1] = 1
        
for i in range(2, n):
    for start in range(n - i):
        end = start + i
        
        if nums[start] == nums[end]:
            if dp[start + 1][end - 1] == 1:
                dp[start][end] = 1
                
for _ in range(m):
    s, e = map(int, input().split())
    print(dp[s - 1][e - 1])
    

문제풀이

처음 보면 reversed()를 사용해서 역순으로 만든 리스트로 비교하여 팰린드롬인지 확인하는 풀이법이 떠오르겠지만, 문제난이도가 골드4이기도하고 시간복잡도를 계산해봐도 수열의 크기는 최대 2000이고, 질문의 개수가 1,000,000이므로 단순 계산 해도 20억의 시간복잡도를 가지기 때문에 일일히 reversed로 주어진 팰린드롬을 뒤집으면 시간초과가 난다.

따라서 다른 방법을 생각해야하는데, 팰린드롬의 성질에 대해 먼저알아야 한다.

121 의 팰린드롬이 있다면, 41214도 팰린드롬이다. 따라서 가장 작은 팰린드롬으로 부터 맨 앞과 맨뒤의 숫자를 비교해서 둘이 같다면, 그 숫자도 팰린드롬임을 알 수 있다.

따라서 n * n의 dp 배열을 만들어주고, 가장 작은 팰린드롬으로부터 시작해 숫자를 하나씩 추가해가며 나올 수 있는 팰린드롬 여부를 모두 조사해 배열을 채워준뒤 이를 m번의 질문에 대답하면 된다. 이렇게 할 경우, 2,000 * 2,000 + 1,000,000 = 5,000,000정도로 문제를 풀이 할 수 있으므로 약 5000만번의 연산을 하는 0.5초의 시간제한을 통과할 수 있다.