백준 10942 팰린드롬? 문제 풀이
문제 파악하기
이 문제는 매우 빡빡한 시간 조건과 매우 넓은 범위의 입력값을 가진 문제입니다.
언듯 보면 팰린드롬 여부만 파악하면 될 것 같지만, 1십만 개의 숫자 배열에 대해 최대 1백만회 일정 범위에 대해 팰린드롬에 대해 물어볼 수 있으므로 팰린드롬 관련 처리에 집중한다면 시간 초과가 발생하기 쉬워보입니다.
문제 풀어보기
어떠한 범위의 수열이 팰린드롬인지 쿼리하면, 그 범위 내의 수는 최소한 1회 이상은 그 값을 확인하는 과정을 거쳐야 합니다.
1백만회에 이르는 쿼리들이 요구하는 부분 수열의 범위는 서로 부분적으로 겹칠 가능성이 매우 높습니다. 따라서 쿼리 중 부분 수열의 팰린드롬 확인 결과만 저장하더라도 반복되는 부분 수열 쿼리를 획기적으로 생략할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def is_pal(self, init: int, fin: int) -> bool:
...
if fin - init > 1:
pal = self.is_pal(init + 1, fin - 1)
if not pal:
self.dp[init][fin] = False
else:
if nums[init] == nums[fin]:
self.dp[init][fin] = True
else:
self.dp[init][fin] = False
else:
if nums[init] == nums[fin]:
self.dp[init][fin] = True
else:
self.dp[init][fin] = False
...