원래 나의 풀이
### 백준
## 펠린드롬? 10942번
# Dynamic Programming
n = int(input())
lst = input().split()
lst = "".join(lst)
t = int(input())
for _ in range(t):
s,e = map(int, input().split())
check = lst[s-1:e]
if check == check[::-1]:
print(1)
else:
print(0) 정말 단순하게 문자열 슬라이싱을 이용해 펠린드롬 여부를 판단하여 문제를 풀었다. 결과는 시간초과...
저번에도 leetcode에서 펠린드롬 문제를 풀어보았고 펠린드롬 여부를 판단하기 위해서 문자열 슬라이싱이 가장 빠른 방법이라 했기에 굉장히 의아하였다.
그렇지만 테스트케이스가 M (1 ≤ M ≤ 1,000,000)이 주어진다면 얘기가 달라질 것이다. 문자열이 같은지 다른지 확인하려면 문자열의 길이 만큼의 시간이 걸린다. 그렇다면 O(n^2 * m)의 엄청난 시간이 걸린다.
그렇다면 테스트케이스를 M의 크기를 무시할 방법은 메모이제이션을 통해 답을 저장해놓고 바로바로 출력할 수 있는 방법을 생각해보았다.
시간 복잡도를 최소로 하고 메모이제이션을 이용하는 방법이므로 DP를 쉽게 떠올릴 수 있었다. 펠린드롬 특성상 문자열의 길이가 1일 경우 펠린드롬이고 문자열의 길이가 1보다 클 경우 문자열의 길이의 처음과 끝이 같고 그 안에 있는 문자열이 펠린드롬이라는 메모이제이션이 있을 경우 DP를 실현할 수 있을 것이다.
하지만 이 방법에서 구현이 어려워 남의 코드를 살..짝 보았다.
메모이제이션은 2차원 배열을 통해서 구현했다.
1) 문자열의 길이가 1일 경우 펠린드롬이므로 1이라고 표시한다.
for i in range(n):
for j in range(n-i):
# 펠린드롬의 문자열의 길이 == 1
if i == 0:
dp[j][j] = 1이렇게 이중 포문으로 표시한 이유는
for i in range(n):
for j in range(n-i):표를 대각선으로 채워나가기 위해서이다.
i는 문자열의 길이를 뜻하고
j는 문자열 길이에 대해서 나올 수 있는 단어들이라고 보시면 될 것 같다.
ex)
i = 3, j = 1이면
7
1 2 1 3 1 2 1에서 (2,1,3)의 문자열에 대한 정보를 넣게 될 것이다.
2) 문자열의 길이가 2일 경우 문자열 처음과 끝을 비교해 같으면 1이라고 표시한다.
# 펠린드롬의 문자열의 길이 == 2
elif i == 1:
if lst[j] == lst[j+1]:
dp[j][j+1] = 1
3) 문자열의 길이가 3이상일 경우 문자열 처음과 끝을 비교해 같아야하고 추가로 그 안에 있는 문자열이 펠린드롬이어야 한다.
else:
# 처음과 끝의 문자가 같고 처음과 끝을 제외한 문자열이 펠린드롬일 때
if lst[j] == lst[i+j] and dp[j+1][i+j-1] == 1:
dp[j][i+j] = 1
dp[j+1][i+j-1]은 안에 있는 문자열이 펠린드롬인지 나타내는 dp의 위치이다.
4) 전체 코드
### 백준
## 펠린드롬? 10942번
# Dynamic Programming
import sys
input = sys.stdin.readline
n = int(input())
lst = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n-i):
# 펠린드롬의 문자열의 길이 == 1
if i == 0:
dp[j][j] = 1
# 펠린드롬의 문자열의 길이 == 2
elif i == 1:
if lst[j] == lst[j+1]:
dp[j][j+1] = 1
# 펠린드롬의 문자열의 길이 >= 3
else:
# 처음과 끝의 문자가 같고 처음과 끝을 제외한 문자열이 펠린드롬일 때
if lst[j] == lst[i+j] and dp[j+1][i+j-1] == 1:
dp[j][i+j] = 1
t = int(input())
for i in range(t):
s,e = map(int, input().split())
print(dp[s-1][e-1])