개요
문자열이 하나 주어졌을 때, 해당 문자열에서 발견할 수 있는 모든 회문(palindrome) 부분 문자열을 찾는 문제를 살펴보겠습니다. 여기서 중요한 점은 동일한 회문이라도 위치가 다르면 서로 다른 부분 문자열로 간주한다는 것입니다. 예를 들어 'aa'가 두 번 등장하면 두 개의 별도 부분 문자열로 셉니다.
입력이 redivider라고 가정해 보겠습니다. 이 문자열은 전체적으로 좌우 대칭이므로 다음과 같은 출력 결과를 얻게 됩니다.
['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider', 'i', 'd', 'e', 'r']
알고리즘 접근 방식
이 문제를 해결하기 위해 중심 확장(center expansion) 기법을 활용합니다. 핵심 아이디어는 0.5씩 증가하는 소수 위치를 사용하여 홀수 길이와 짝수 길이의 회문을 모두 처리하는 것입니다.
구체적인 단계는 다음과 같습니다.
- 결과를 저장할 빈 리스트 v를 생성합니다.
- 위치 pos를 0.0으로 초기화합니다.
- pos가 문자열 길이보다 작은 동안 반복합니다.
- rad := pos - int(pos)로 반지름을 계산합니다.
- (pos + rad)가 문자열 범위 안에 있고, (pos - rad)가 0 이상이며, s[int(pos - rad)]와 s[int(pos + rad)]가 같은 동안:
- s[int(pos - rad) : int(pos + rad + 1)] 구간을 v의 끝에 추가합니다.
- rad를 1 증가시켜 확장 범위를 넓힙니다.
- pos를 0.5씩 증가시킵니다.
- v를 반환합니다.
동작 원리 설명
pos가 정수일 때(예: 0.0, 1.0, 2.0) rad는 0부터 시작하므로 단일 문자에서 출발해 양쪽으로 확장하며 홀수 길이의 회문을 찾습니다. 반면 pos가 x.5 형태일 때 rad는 0.5부터 시작하므로 인접한 두 문자를 중심으로 확장하며 짝수 길이의 회문을 찾습니다. 이렇게 하면 별도의 분기 처리 없이 모든 경우의 수를 우아하게 커버할 수 있습니다.
예제 코드
다음 구현 예제를 통해 더 잘 이해해 보겠습니다.
def get_all_pal_sub(s):
v = []
pos = 0.0
while pos < len(s):
rad = pos - int(pos)
while ((pos + rad) < len(s) and (pos - rad) >= 0
and (s[int(pos - rad)] == s[int(pos + rad)])):
v.append(s[int(pos - rad): int(pos + rad + 1)])
rad += 1
pos += 0.5
return v
v = get_all_pal_sub("redivider")
print(len(v))
print(v)입력
"redivider"
출력
13 ['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider', 'i', 'd', 'e', 'r']
마무리
이 방법은 시간 복잡도가 O(n²)로, 브루트 포스 방식(O(n³))보다 효율적입니다. 문자열의 각 위치를 중심으로 회문인 동안 계속 확장하기 때문에 불필요한 비교를 줄일 수 있습니다. 회문 관련 문제를 풀 때 중심 확장 기법은 매우 유용하게 활용되는 패턴이므로, 꼭 익혀두시기 바랍니다.