문제 이해하기
소문자 영어 알파벳으로만 이루어진 두 문자열 s와 t가 주어졌다고 가정해 봅시다. 우리가 구해야 할 것은 각각 (l, k) 형태를 가지는 세 개의 쌍(pair)으로 이루어진 리스트입니다. 여기서 k는 문자열, l은 해당 문자열의 길이를 의미합니다.
세 쌍은 다음과 같이 구성됩니다.
- 첫 번째 쌍: 두 문자열에서 가장 긴 공통 접두사(longest common prefix)인 p
- 두 번째 쌍: 공통 접두사를 제거한 후 s에 남은 부분 s'
- 세 번째 쌍: 공통 접두사를 제거한 후 t에 남은 부분 t'
따라서 최종 결과는 [(len(p), p), (len(s'), s'), (len(t'), t')] 형태가 됩니다.
예시
입력이 s = "science", t = "school"이라면 출력은 다음과 같습니다.
[(2, 'sc'), (5, 'ience'), (4, 'hool')]
"science"와 "school"의 공통 접두사는 "sc"이며, 접두사를 제거하고 남은 부분은 각각 "ience"와 "hool"입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 빈 문자열로 lcp를 초기화합니다.
- i를 0부터 s와 t 중 더 짧은 문자열의 길이까지 반복하면서, s[i]와 t[i]가 같으면 해당 문자를 lcp에 추가합니다.
- s_rem을 s에서 인덱스 len(lcp)부터 끝까지의 부분 문자열로 설정합니다.
- t_rem도 같은 방식으로 설정합니다.
- [(len(lcp), lcp), (len(s_rem), s_rem), (len(t_rem), t_rem)] 리스트를 반환합니다.
이 알고리즘의 시간 복잡도는 두 문자열 중 짧은 쪽의 길이에 비례하는 O(min(len(s), len(t)))입니다.
구현 예제
아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
def solve(s, t):
lcp = ''
for i in range(min(len(s), len(t))):
if s[i] == t[i]:
lcp += s[i]
s_rem = s[len(lcp):]
t_rem = t[len(lcp):]
return [(len(lcp), lcp), (len(s_rem), s_rem), (len(t_rem), t_rem)]
s = "science"
t = "school"
print(solve(s, t))입력
"science", "school"
출력
[(2, 'sc'), (5, 'ience'), (4, 'hool')]
추가 팁
파이썬 표준 라이브러리의 os.path.commonprefix() 함수를 활용하면 공통 접두사를 한 줄로 구할 수 있어 코드를 더욱 간결하게 만들 수 있습니다. 다만 이 함수는 경로뿐 아니라 일반 문자열에도 동작한다는 점을 기억해 두면 유용합니다.