10942

오답 여부: o

편집 시간: 2022년 3월 15일 오후 2:35

코드

Algorithm/10942.py at main · Junroot/Algorithm

풀이

질문의 개수가 최대 1,000,000개이므로 질문하는 순간 팰린드롬을 계산하면 시간 초과가 발생한다는 것을 알 수 있다. 그러면 미리 팰린드롬을 계산해둬야 되는데 수열의 크기가 최대 2,000이므로 O(N^2)내로 해결해야된다.

어떤 팰린드롬이 있을 때 이 수열의 왼쪽, 오른쪽에 같은 수를 붙이면 계속 팰린드롬이라는 성질을 이용해 문제를 접근했다.

잘못된 풀이

나는 위의 성질을 이용해서 길이가 1, 2인 팰린드롬들을 구하고 이 팰린드롬에서 왼쪽과 오른쪽을 늘리면서 구할 수 있는 모든 팰린드롬을 구했다. 아래 코드가 그 과정이다. 하지만 union에서 시간이 많이 발생하는지 시간 초과가 발생했다.

from collections import deque
from sys import stdin

n = int(input())
numbers = list(map(int, input().split()))
new_ranges = deque([(i, i) for i in range(n)]) # 길이가 1인 수열은 모드 팰린드롬이다.


for i in range(n - 1):
    if numbers[i] == numbers[i + 1]:
        new_ranges.append((i, i + 1))

ranges = set()
for _ in range(n // 2):
    ranges = ranges.union(new_ranges)
    for _ in range(len(new_ranges)):
        start, end = new_ranges.popleft()
        if start == 0 or end == n - 1:
            continue
        if numbers[start - 1] == numbers[end + 1]:
            new_ranges.append((start - 1, end + 1))

m = int(input())

for _ in range(m):
    start, end = map(int, stdin.readline().split())
    if (start - 1, end - 1) in ranges:
        print("1")
    else:
        print("0")

맞는 풀이

결국 다른 사람 풀이를 조금 참고했다. 기본적인 알고리즘은 같았는데, 이중 배열을 사용해서 팰린드롬을 관리했다. palindromes[start][end]는 start부터 end까지의 수열이 팰린드롬이면 1, 아니면 0을 나타내고 있다. palindromes[start][end] 값을 구할 때, palindromes[start-1][end+1] 이 필요하므로, 길이가 작은 수열을 우선적으로 계산하는 식으로 구현했다.

from sys import stdin

n = int(input())
numbers = list(map(int, input().split()))
palindromes = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    palindromes[i][i] = 1

for i in range(n - 1):
    if numbers[i] == numbers[i + 1]:
        palindromes[i][i + 1] = 1

for length in range(3, n + 1):
    for i in range(n - length + 1):
        start = i
        end = i + length - 1
        if numbers[start] == numbers[end] and palindromes[start + 1][end - 1] == 1:
            palindromes[start][end] = 1

m = int(input())

for _ in range(m):
    start, end = map(int, stdin.readline().split())
    print(palindromes[start - 1][end - 1])

코드#

풀이#

잘못된 풀이#

맞는 풀이#

코드

풀이

잘못된 풀이

맞는 풀이