문제 설명
두 개의 문자열 s와 t가 주어져 있다고 가정해 봅시다. 다음 규칙에 따라 merge라는 새로운 문자열을 만들어야 합니다. s 또는 t 중 하나라도 비어 있지 않은 동안, 아래 작업 중 하나를 반복적으로 수행합니다.
- s가 비어 있지 않으면, s의 첫 번째 문자를 merge 끝에 추가하고 s에서 제거합니다.
- t가 비어 있지 않으면, t의 첫 번째 문자를 merge 끝에 추가하고 t에서 제거합니다.
목표는 이렇게 만들 수 있는 병합 결과 중 사전순(lexicographically)으로 가장 큰 문자열을 찾는 것입니다.
예를 들어 s = "zxyxx", t = "yzxxx"가 입력으로 주어지면 출력은 zyzxyxxxxx가 됩니다. 과정은 다음과 같습니다.
- s에서 선택: merge = "z", s = "xyxx", t = "yzxxx"
- t에서 선택: merge = "zy", s = "xyxx", t = "zxxx"
- t에서 선택: merge = "zyz", s = "xyxx", t = "xxx"
- s에서 선택: merge = "zyzx", s = "yxx", t = "xxx"
- s에서 선택: merge = "zyzxy", s = "xx", t = "xxx"
마지막으로 s와 t에 남아 있는 5개의 'x'를 merge 뒤에 이어 붙이면 완성됩니다.
접근 방법
사전순으로 가장 큰 결과를 얻으려면 매 순간 그리디(greedy)하게 선택해야 합니다. 핵심은 현재 남아 있는 두 문자열의 나머지 부분 전체를 비교한 뒤, 더 큰 쪽의 첫 문자를 가져오는 것입니다. 알고리즘은 다음과 같습니다.
- ans := 빈 문자열
- idx1 := 0, idx2 := 0
- idx1이 s의 길이보다 작고 idx2가 t의 길이보다 작은 동안 반복:
- s[idx1] > t[idx2]이거나, (s[idx1] == t[idx2]이면서 s[idx1:] >= t[idx2:])인 경우 → ans에 s[idx1]을 붙이고 idx1을 1 증가
- 그 외의 경우(s[idx1] < t[idx2]이거나, 같은 문자이면서 s[idx1:] <= t[idx2:]) → ans에 t[idx2]를 붙이고 idx2를 1 증가
- 반복이 끝나면 ans + s[idx1:] + t[idx2:]를 반환합니다.
핵심 포인트
두 문자열의 현재 문자가 서로 같을 때는 단순히 아무 쪽이나 선택하면 안 됩니다. 이 경우 각 문자열의 접미사(s[idx1:]과 t[idx2:])를 통째로 비교하여 더 큰 쪽에서 문자를 가져와야 최종 결과가 사전순으로 가장 커집니다. 이것이 이 문제 해결의 핵심 아이디어입니다.
Python 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
def solve(s, t):
ans = ""
idx1 = idx2 = 0
while(idx1<len(s) and idx2<len(t)):
if s[idx1]>t[idx2] or (s[idx1]==t[idx2] and s[idx1:]>=t[idx2:]):
ans+=s[idx1]
idx1+=1
elif s[idx1]<t[idx2] or (s[idx1]==t[idx2] and s[idx1:]<=t[idx2:]):
ans+=t[idx2]
idx2+=1
return ans+s[idx1:]+t[idx2:]
s = "zxyxx"
t = "yzxxx"
print(solve(s, t))
입력
s = "zxyxx", t = "yzxxx"
출력
zyzxyxxxxx
시간 복잡도
반복문이 실행될 때마다 문자열 슬라이싱 비교가 발생하므로, 최악의 경우 시간 복잡도는 O((len(s) + len(t)) × min(len(s), len(t)))가 됩니다. 성능이 중요하다면 슬라이싱 대신 인덱스 기반 비교를 사용하거나, 접미사 배열 등의 자료구조를 활용해 최적화할 수 있습니다.