문제 개요
소문자로만 구성된 문자열 s가 주어졌을 때, 문자열 안에서 최소 두 번 이상 등장하는 가장 긴 부분 문자열의 길이를 구해야 합니다. 만약 두 번 이상 나타나는 부분 문자열이 존재하지 않는다면 0을 반환합니다.
예를 들어 입력이 s = "abdgoalputabdtypeabd"라면 결과는 3입니다. 왜냐하면 두 번 이상 등장하는 가장 긴 부분 문자열이 바로 "abd"이고, 그 길이가 3이기 때문입니다.
해결 전략: 접미사(Suffix) 비교 방식
이 문제는 접미사 배열을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 문자열의 모든 접미사(특정 위치부터 끝까지의 부분 문자열)를 생성합니다.
- 접미사들을 사전순으로 정렬합니다.
- 정렬된 상태에서는 서로 인접한 두 접미사가 가장 많은 공통 접두사를 가질 가능성이 높습니다.
- 따라서 인접한 접미사 쌍들의 공통 접두사 길이를 비교하여 그중 최댓값을 구하면 됩니다.
알고리즘 단계별 설명
- lcs(s1, s2) 함수를 정의합니다. 이 함수는 두 문자열이 공유하는 가장 긴 접두사(prefix)를 반환합니다.
- 먼저 n := min(len(s1), len(s2))로 두 문자열 길이 중 작은 값을 구합니다.
- i를 0부터 n-1까지 순회하면서 s1[i]와 s2[i]가 다른 지점을 발견하면, 그 앞부분인 s1[:i]를 반환합니다.
- 모든 위치가 같다면 s1[:n]을 반환합니다.
- 메인 로직에서는 다음을 수행합니다.
- n := len(s), max_len := 0으로 초기화합니다.
- i를 0부터 n-1까지 순회하며 각 위치 i에서 시작하는 접미사 s[i:n]을 리스트에 추가합니다.
- 접미사 리스트를 오름차순으로 정렬합니다.
- zip()을 사용해 인접한 접미사 쌍 (a, b)를 순회하며 lcs(a, b)의 길이를 계산하고, max_len보다 크면 갱신합니다.
- 최종적으로 max_len을 반환합니다.
Python 구현 예제
def lcs(s1, s2):
n = min(len(s1), len(s2))
for i in range(n):
if s1[i] != s2[i]:
return s1[:i]
return s1[:n]
def solve(s):
suffixes = []
n = len(s)
max_len = 0
for i in range(n):
suffixes.append(s[i:n])
suffixes.sort()
for a, b in zip(suffixes, suffixes[1:]):
rtr = lcs(a, b)
if len(rtr) > max_len:
max_len = len(rtr)
return max_len
s = "abdgoalputabdtypeabd"
print(solve(s))입력
"abdgoalputabdtypeabd"
출력
3
동작 원리 살펴보기
위 예제에서 문자열 "abdgoalputabdtypeabd"의 접미사들을 정렬하면, "abd"로 시작하는 접미사들이 서로 인접하게 배치됩니다. 이때 인접한 두 접미사의 공통 접두사가 "abd"(길이 3)이 되므로, 최종 결과로 3이 반환됩니다.
시간 복잡도 분석
- 접미사 생성: O(n²) — 각 위치마다 최대 n 길이의 문자열을 복사합니다.
- 정렬: O(n log n)번의 비교가 발생하고, 각 비교에 최대 O(n)이 걸릴 수 있으므로 전체적으로 O(n² log n)입니다.
- 인접 접미사 비교: O(n²) — 각 비교에 최대 O(n)이 소요됩니다.
입력 크기가 수천 자 이내라면 이 방법으로 충분히 빠르게 동작하지만, 더 큰 입력에는 접미사 배열 + LCP 배열 또는 이진 탐색 + 롤링 해시 기반의 고급 알고리즘을 고려하는 것이 좋습니다.