문제 이해하기
두 개의 문자열 s와 t가 주어졌다고 가정해 봅시다. 우리는 다음 규칙에 따라 'merge'라는 새로운 문자열을 만들어야 합니다.
s 또는 t 중 하나라도 비어 있지 않은 동안, 아래 두 가지 동작 중 하나를 선택해 수행합니다.
- s가 비어 있지 않다면, s의 첫 번째 문자를 merge 끝에 붙이고 해당 문자를 s에서 제거합니다.
- t가 비어 있지 않다면, t의 첫 번째 문자를 merge 끝에 붙이고 해당 문자를 t에서 제거합니다.
이렇게 만들 수 있는 병합 문자열 중 사전순으로 가장 큰(lexicographically largest) 결과를 구하는 것이 목표입니다.
예를 들어 입력이 s = "zxyxx", t = "yzxxx"라면, 정답은 "zyzxyxxxxx"가 됩니다.
접근 방법: 탐욕(Greedy) 전략
이 문제의 핵심은 매 순간 남아 있는 문자열 전체(접미사)를 비교하는 것입니다. 단순히 현재 맨 앞 문자 하나만 비교하면 안 되고, s[a:]와 t[b:]처럼 각 문자열의 나머지 부분 전체를 비교한 뒤 더 큰 쪽에서 문자를 가져오는 것이 최적의 선택입니다.
구체적인 해결 단계는 다음과 같습니다.
- 포인터 a = 0, b = 0으로 초기화합니다. (a는 s의 현재 위치, b는 t의 현재 위치)
- merge를 빈 문자열로 초기화하고, W1 = len(s), W2 = len(t)를 저장합니다.
- a < W1이고 b < W2인 동안 반복합니다.
- s[a:] > t[b:]라면, 즉 s의 나머지 부분이 더 크다면 merge에 s[a]를 붙이고 a를 1 증가시킵니다.
- 그렇지 않다면 merge에 t[b]를 붙이고 b를 1 증가시킵니다.
- 반복이 끝나면 merge + s[a:] + t[b:]를 반환합니다. (남은 문자열은 어느 쪽이든 모두 붙여주면 됩니다.)
예제 코드
아래 파이썬 구현을 통해 더 잘 이해할 수 있습니다.
def solve(s, t):
a = b = 0
merge = ""
W1 = len(s)
W2 = len(t)
while a < W1 and b < W2:
if s[a:] > t[b:]:
merge += s[a]
a += 1
else:
merge += t[b]
b += 1
return merge + s[a:] + t[b:]
s = "zxyxx"
t = "yzxxx"
print(solve(s, t))입력
"zxyxx", "yzxxx"
출력
zyzxyxxxxx
동작 원리 살펴보기
위 예제에서 처음 상태는 s = "zxyxx", t = "yzxxx"입니다. s[a:] = "zxyxx"가 t[b:] = "yzxxx"보다 크므로 'z'를 먼저 가져옵니다. 이후에도 매 단계마다 나머지 접미사를 비교하며 더 큰 쪽에서 문자를 가져오기 때문에, 최종적으로 사전순으로 가장 큰 병합 결과 "zyzxyxxxxx"를 얻게 됩니다.
시간 복잡도 측면에서 보면, 매번 슬라이싱으로 접미사를 비교하므로 대략 O((len(s) + len(t)) × len(s) × len(t)) 수준이지만, 문제의 일반적인 입력 범위에서는 충분히 효율적으로 동작합니다.