문자열 s가 주어졌을 때, s의 뒤에 문자를 덧붙여 회문(palindrome)을 완성해야 한다고 가정해 보겠습니다. 이때 추가해야 하는 최소 문자 수를 구하는 것이 이 글의 목표입니다.
예를 들어 입력이 s = "mad"라면, 뒤에 "am"을 붙여 "madam"이라는 회문을 만들 수 있으므로 정답은 2가 됩니다. 반면 이미 회문인 "madam"이 입력되면 추가할 문자가 전혀 필요 없으므로 결과는 0입니다.
풀이 접근 방법
핵심 아이디어는 문자열에서 가장 긴 팰린드롬 접미사(suffix)를 찾는 것입니다. 팰린드롬 접미사가 시작되는 인덱스가 곧 추가해야 할 문자 수와 같습니다. 아래 알고리즘은 롤링 해시(rolling hash) 기법을 사용해 정방향 해시와 역방향 해시를 비교하면서 선형 시간(O(n))에 답을 구합니다.
다음 단계를 따릅니다.
b := 256, m := 10^9 + 7 (해시 계산에 쓰이는 밑수와 모듈러 값)
s := 문자열의 각 문자를 (ASCII 코드 − 97) 값으로 변환한 리스트
r := s의 마지막 요소, l := s의 마지막 요소 (정방향·역방향 해시의 초기값)
n := s의 크기
res := n − 1 (최악의 경우 마지막 한 글자만 팰린드롬 접미사)
p := b
i를 n − 2부터 0까지 1씩 줄여 가며 반복합니다.
r := (r + s[i] × p) mod m
l := (l × b + s[i]) mod m
p := (p × b) mod m
만약 l과 r이 같다면 s[i..n−1] 구간은 팰린드롬이므로 res := i로 갱신합니다.
res를 반환합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
예제 코드
class Solution:
def solve(self, s):
b = 256
m = 10 ** 9 + 7
s = list(ord(i) - 97 for i in s)
r = l = s[-1]
n = len(s)
res = n - 1
p = b
for i in range(n - 2, -1, -1):
r += s[i] * p
r %= m
l *= b
l += s[i]
l %= m
p *= b
p %= m
if l == r:
res = i
return res
ob = Solution()
s = "mad"
print(ob.solve(s))
입력
"mad"
출력
2
복잡도 분석
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 변환된 문자 리스트를 저장하기 위한 공간 복잡도 역시 O(n)입니다. 또한 큰 소수 모듈러(m = 10^9 + 7)를 함께 사용하기 때문에 해시 충돌 가능성은 실질적으로 무시할 수 있는 수준으로 낮아집니다.