문자열 'input_str'이 주어졌다고 가정해 보겠습니다. 이 문자열로부터 만들 수 있는 모든 접미사(suffix)를 구한 뒤, 원래 문자열과 각 접미사 사이의 유사도를 계산하는 것이 이번 문제입니다. 여기서 유사도란 원래 문자열과 해당 접미사가 공유하는 가장 긴 공통 접두사(longest common prefix)의 길이로 정의되며, 최종적으로는 모든 접미사와의 유사도 합을 반환해야 합니다.
예를 들어 입력이 input_str = 'tpotp'라면 출력은 7이 됩니다.
'tpotp'에서 만들 수 있는 모든 접미사는 'tpotp', 'potp', 'otp', 'tp', 'p'입니다.
각 접미사와 원래 문자열의 유사도를 하나씩 확인해 보면 다음과 같습니다.
'tpotp' 유사도 5 'potp' 유사도 0 'otp' 유사도 0 'tp' 유사도 2 'p' 유사도 0 유사도의 합 = 5 + 0 + 0 + 2 + 0 = 7
풀이 방법: Z-알고리즘 활용
모든 접미사를 일일이 비교하면 시간 복잡도가 O(n²)까지 늘어날 수 있습니다. 이 문제는 Z-알고리즘의 아이디어를 적용하면 선형 시간 O(n)에 가깝게 효율적으로 해결할 수 있습니다. 알고리즘의 진행 단계는 다음과 같습니다.
- return_list := input_str의 길이(len(input_str))를 첫 요소로 갖는 새로운 리스트
- i := 1, p := 0, q := 0, r := 0으로 초기화
- i가 input_str의 길이보다 작은 동안 다음을 반복합니다.
- q < i < (q + p)인 경우:
- return_list[i - q] ≥ (q + p - i)이면 → r := q + p - i로 설정한 뒤, p와 q를 0으로 초기화하여 직접 비교 모드로 전환합니다.
- 그렇지 않으면 → 이미 계산된 값을 재활용하여 return_list 끝에 return_list[i - q]를 추가하고, i를 1 증가시키며 r을 0으로 초기화합니다.
- 그 외의 경우:
- (i + r이 문자열 길이보다 작으면서) input_str[r]과 input_str[i + r]이 같은 동안 r을 1씩 증가시킵니다.
- r의 값을 return_list에 추가합니다.
- p := r, q := i로 갱신한 뒤, i를 1 증가시키고 r을 0으로 초기화합니다.
- q < i < (q + p)인 경우:
- 반복이 끝나면 return_list의 모든 요소의 합을 반환합니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
def solve(input_str):
return_list = [len(input_str)]
i = 1
p, q = 0, 0
r = 0
while i < len(input_str):
if q < i < (q + p):
if return_list[i - q] >= q + p - i:
r = q + p - i
p, q = 0, 0
else:
return_list.append(return_list[i - q])
i += 1
r = 0
else:
while i + r < len(input_str) and input_str[r] == input_str[i + r]:
r += 1
return_list.append(r)
p, q = r, i
i += 1
r = 0
return sum(return_list)
print(solve('tpotp'))
참고: return 문은 반드시 while 루프 바깥에 위치해야 합니다. 루프 내부에 있으면 첫 번째 반복 후 즉시 함수가 종료되어 잘못된 결과가 반환됩니다.
입력
'tpotp'
출력
7