[BOJ] 16570 - 앞뒤가 맞는 수열 (Python)

 

 

아이디어

 

수열을 뒤집어 KMP 알고리즘으로 접근한다.

 

 

풀이

 

수열 리스트 A를 뒤집어 저장한 다음, 부분 일치 테이블 lps에 일치하는 길이를 저장한다.

앞뒤수열이 존재하면 lps에서 가장 큰 값(앞뒤계수 최댓값)과 그 개수를 출력하고, 그렇지 않으면 -1을 출력한다.

 

N = int(input())
A = list(map(int, input().split()))[::-1]
lps = [0]*N
j = 0
for i in range(1, N):
    while j > 0 and A[i] != A[j]:
        j = lps[j-1]
    if A[i] == A[j]:
        j += 1
        lps[i] = j
max_len = max(lps)
if max_len > 0:
    print(max_len, lps.count(max_len))
else:
    print(-1)

 

 

리스트를 뒤집는 것보다 음수 인덱스로 접근하는 코드가 더 빠를 줄 알았는데, 오히려 더 느렸다.

# 더 느린 코드
lps = [-1]*N
j = -1
for i in range(-2, -(N+1), -1):
    while j < -1 and A[i] != A[j]:
        j = lps[j+1]
    if A[i] == A[j]:
        j -= 1
        lps[i] = j
min_val = min(lps)
if min_val < -1:
    print(-(min_val+1), lps.count(min_val))
else:
    print(-1)