입력
첫째 줄에 수열의 크기가 주어짐
둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어짐
셋째 줄에는 홍준이가 한 질문의 개수가 주어짐
넷째 줄부터 M개의 줄에는 홍준이가 한 질문 s,e가 한 줄에 하나씩 주어짐
출력
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서대로 출력, 팰린드롬인 경우 1, 아닌 경우 0을 출력
풀이 1 : Two-Pointer, Dp : 시간 초과 !
# Two Pointer, DP : 시간 초과!
import sys
n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
m = int(sys.stdin.readline())
d = [[None for _ in range(n+1)] for _ in range(n+1)]
# d[i][j]가 0이면 i~j 팰린드롬 x, 1이면 팰린드롬 o
def is_pailndrome(arr:list, s:int, e:int):
i = s-1; j = e-1
while i < j:
if d[i+1][j+1]: break
if arr[i] != arr[j]: return 0
i += 1; j -= 1
return 1
for _ in range(m):
s, e = map(int,sys.stdin.readline().split())
result = is_pailndrome(arr, s, e)
if result:
while s < e:
d[s][e] = 1
s += 1; e -= 1
print(result)
풀이 2 : 부분 문자열 팰린드롬 판별 알고리즘 : O(n^2)
간격을 기준(간격 0, 간격 1, 간격 k)으로 순회문을 돌면서 dp 테이블을 채우는 바텀업 방식의 다이나믹 프로그래밍 알고리즘 방식을 사용하여 구현하였다.
# DP : bottom-up, O(n^2)
import sys
n = int(input())
string = list(map(int,sys.stdin.readline().split()))
d = [[0 for _ in range(n)] for _ in range(n)]
# d[x][y] : x+1번째부터 y+1번째까지 팰린드인지 저장하는 테이블
# 간격 0 : 자기 자신은 항상 팰린드롬
for i in range(0, n): # 0~n-1
d[i][i] = 1
# 간격 1 : i와 i+1이 같다면 팰린드롬
for i in range(0, n-1): # 0,(1)~n-2,(n-1)
if string[i] == string[i+1]:
d[i][i+1] = 1
# 간격 k(2~n-1)
for k in range(2, n): # 2~n-1
for i in range(0, n-k): # 0,(k)~n-1-k,(n-1)
j = i + k
if (string[i] == string[j]) and (d[i+1][j-1] == 1):
d[i][j] = 1
m = int(input())
for _ in range(m):
s, e = map(int,sys.stdin.readline().split())
print(d[s-1][e-1])
풀이 3 : Manacher 알고리즘 : O(n)
입력된 숫자 사이에 #을 끼워서 1,1,1 -> #,1,#,1,#,1로 만들면 1,1(짝수 부분 수열)의 회문 여부를 1,#,1의 #의 dp 테이블 값으로 판단할 수 있다.
입력된 수열의 길이를 n->2*n으로 수정해 주고
각각의 인덱스를 2+index+1로 대응해서 생각하면 된다.(0번->1번, 1번->3번...)
# Manacher's Algorithm, O(n)
import sys
n = int(input()); n *= 2
# 입력된 숫자 사이에 #을 끼워 넣어서 1,1,1 -> #,1,#,1,#,1
# 1,1의 회문 여부를 1,#,1로 판단할 수 있다.
line = list(map(int,sys.stdin.readline().split())); s = []
for x in line:
s.append("#"); s.append(x)
d = [0 for _ in range(n)]
def manacher(s:str, n:int):
right = 0; center = 0
for i in range(n):
if i <= right:
d[i] = min(d[2*center-i], right-i)
while (i-d[i] > 0 and i+d[i] < n-1) and (s[i-(d[i]+1)] == s[i+(d[i]+1)]):
d[i] += 1
if i + d[i] > right:
right = i + d[i]
center = i
manacher(s, n)
m = int(input())
for _ in range(m):
s, e = map(int,sys.stdin.readline().split())
s = 2*(s-1)+1; e = 2*(e-1)+1; center = int((s+e)/2)
print(1) if center+d[center] >= e else print(0)