문제 정의
소문자 ASCII 문자로만 구성된 문자열이 주어졌을 때, 해당 문자열 안에 존재하는 모든 고유한(중복 없는) 연속 회문(palindrome) 부분 문자열을 찾아야 합니다.
예를 들어 입력 문자열이 "bddaaa"라면, 찾아야 할 회문들은 다음과 같습니다.
[a, aa, aaa, b, d, dd]
풀이 접근 방법
이 문제는 마나커(Manacher) 알고리즘의 원리를 응용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 위치에서 회문을 처음부터 확장하는 대신, 이미 계산된 회문 반지름 정보를 재활용하여 불필요한 비교를 줄이는 것입니다.
단계별 풀이 과정은 다음과 같습니다.
- 발견한 회문을 저장할 딕셔너리(맵)
m을 생성합니다. 딕셔너리의 키는 중복될 수 없으므로 자동으로 중복 회문이 제거됩니다. - 문자열의 길이를
n으로 저장합니다. - 짝수 길이 / 홀수 길이 회문의 반지름 정보를 담기 위해 2행 × (n+1)열 크기의 매트릭스를 0으로 초기화합니다.
- 경계 비교를 단순화하기 위해 문자열 앞에
'@', 뒤에'#'를 붙인 새 문자열을 만듭니다. - j = 0, 1 두 번 반복하면서 각 중심 위치 i에서 좌우 문자가 일치하는 동안 반지름(temp)을 확장하고, 이전에 계산된 값(matrix[j][i-k])을 활용해 여러 위치의 반지름을 한 번에 결정합니다.
- 모든 반지름이 계산되면, 각 위치와 반지름 조합으로 실제 회문 부분 문자열을 슬라이싱하여 맵에 저장합니다.
- 각 단일 문자도 회문이므로 맵에 추가한 뒤, 맵의 모든 키를 출력합니다.
구현 예제
다음은 위 알고리즘을 파이썬으로 구현한 전체 코드입니다.
def find_substr(s):
m = dict()
n = len(s)
matrix = [[0 for x in range(n+1)] for x in range(2)]
s = "@" + s + "#"
for j in range(2):
temp = 0
matrix[j][0] = 0
i = 1
while i <= n:
while s[i - temp - 1] == s[i + j + temp]:
temp += 1
matrix[j][i] = temp
k = 1
while (matrix[j][i - k] != temp - k) and (k < temp):
matrix[j][i+k] = min(matrix[j][i-k], temp - k)
k += 1
temp = max(temp - k, 0)
i += k
s = s[1:len(s)-1]
m[s[0]] = 1
for i in range(1,n):
for j in range(2):
for temp in range(matrix[j][i],0,-1):
m[s[i - temp - 1 : i - temp - 1 + 2 * temp + j]] = 1
m[s[i]] = 1
for i in m:
print (i)
find_substr("bddaaa")
입력
bddaaa
출력
a
aa
b
aaa
d
dd
정리
단순 무식하게 모든 부분 문자열을 검사하면 O(n³)의 시간이 걸리지만, 이 구현은 각 중심점에서 이전 계산 결과를 재활용하므로 훨씬 빠르게 동작합니다. 또한 결과를 딕셔너리에 저장하기 때문에 별도의 중복 검사 없이도 고유한 회문만 깔끔하게 얻을 수 있다는 장점이 있습니다. 참고로 출력 순서는 딕셔너리에 삽입된 순서를 따르므로, 필요하다면 sorted() 함수를 사용해 정렬된 결과를 얻을 수도 있습니다.