파이썬으로 두 문자열을 병합해 사전순으로 가장 큰 문자열 만들기

문제 개요

두 문자열 a와 b가 주어지고, 결과를 담을 문자열 merge가 있다고 가정해 봅시다. 목표는 아래 규칙에 따라 a와 b의 문자를 하나씩 옮겨 merge를 채우는 것입니다.

• 문자열 a가 비어 있지 않으면, a의 첫 번째 문자를 제거해 merge에 추가합니다.
• 문자열 b가 비어 있지 않으면, b의 첫 번째 문자를 제거해 merge에 추가합니다.
• 두 문자열이 모두 비어 있지 않은 경우에는 사전순(lexicographical)으로 더 큰 문자열에서 먼저 문자를 가져옵니다. 즉, a가 b보다 크면 a에서, 그렇지 않으면 b에서 첫 문자를 제거해 merge에 붙입니다.
• a와 b가 모두 빈 문자열이 되면, 지금까지 만든 merge 문자열을 반환합니다.

예제

입력:

a = "bacaa"
b = "abcaa"

출력:

bacabcaaaa

설명: 문자열 a("bacaa")가 b("abcaa")보다 사전순으로 크므로, 처음에는 a에서 문자를 가져옵니다. 이후 매 단계마다 남은 두 문자열을 다시 비교하며 더 큰 쪽에서 문자를 하나씩 뽑아 붙이면 최종적으로 "bacabcaaaa"가 됩니다.

단계별 진행 과정

선택된 문자를 순서대로 이어 붙이면 b → a → c → a → b → c → a → a → a → a, 즉 "bacabcaaaa"가 됩니다.

접근 방법: 그리디(Greedy) 알고리즘

이 문제는 그리디 방식으로 해결할 수 있습니다. 핵심 아이디어는 매 순간 남아 있는 두 문자열 전체를 사전순으로 비교한 뒤, 더 큰 쪽의 첫 문자를 merge에 붙이는 것입니다.

여기서 중요한 점은 첫 글자만 비교해서는 안 된다는 것입니다. 예를 들어 a = "b", b = "bab"인 경우 첫 글자만 보면 같은 'b'지만, 문자열 전체를 비교하면 "bab"가 "b"보다 큽니다. 이렇게 남은 문자열 전체를 비교해야 어느 쪽에서 문자를 가져오는 것이 유리한지 정확하게 판단할 수 있습니다.

알고리즘 단계

1. 두 입력 문자열 a와 b를 받습니다.
2. 결과를 저장할 빈 문자열 ans를 준비합니다.
3. a와 b가 모두 비어 있지 않은 동안 반복합니다.
4. a > b이면 a의 첫 문자를 ans에 추가하고 a에서 제거하고, 그렇지 않으면 b의 첫 문자를 ans에 추가하고 b에서 제거합니다.
5. 반복이 끝나면 남아 있는 문자(a 또는 b)를 ans 뒤에 이어 붙여 반환합니다.

구현 코드

def concatenate_largest(a, b):
    ans = ""
    while a and b:
        if a > b:
            ans += a[0]
            a = a[1:]
        else:
            ans += b[0]
            b = b[1:]
    return ans + a + b

a = "bacaa"
b = "abcaa"
print(concatenate_largest(a, b))

실행 결과

bacabcaaaa

두 문자열 "bacaa"와 "abcaa"는 위 규칙대로 병합하면 "bacabcaaaa"가 됩니다.

복잡도 분석 및 성능 팁

매 반복마다 두 문자열을 비교하므로 한 번의 비교에 최대 O(n)이 걸리고, 이러한 비교가 총 n번(두 문자열 길이의 합) 발생합니다. 따라서 시간 복잡도는 O(n²), 공간 복잡도는 결과 문자열을 저장하기 위해 O(n)입니다.

파이썬에서 문자열은 불변(immutable)이므로 ans += ...를 반복하면 매번 새 문자열이 생성되어 비효율적일 수 있습니다. 길이가 긴 입력에서는 리스트에 문자를 append한 뒤 마지막에 ''.join()으로 합치는 방식이 더 빠릅니다.