C++에서는 두 문자열을 병합하는 다양한 방법이 있지만, 이번 글에서는 두 문자열을 하나로 합치면서 사전순(lexicographical order)으로 가장 큰 결과를 만드는 방법을 알아보겠습니다.
문제 정의
두 문자열 'a'와 'b', 그리고 결과를 저장할 문자열 'merge'가 주어진다고 가정해 봅시다. 다음 규칙에 따라 'merge'를 채워야 합니다.
- 문자열 'a'가 비어 있지 않으면, 'a'의 첫 번째 문자를 꺼내 'merge'에 추가합니다.
- 문자열 'b'가 비어 있지 않으면, 'b'의 첫 번째 문자를 꺼내 'merge'에 추가합니다.
- 두 문자열이 모두 남아 있는 경우에는 사전순으로 더 큰 문자열에서 먼저 문자를 가져옵니다. 예를 들어 'a'가 'b'보다 사전순으로 크다면 'a'의 첫 문자를 먼저 'merge'에 넣습니다.
- 위 과정을 반복하여 모든 문자를 소진하면 완성된 문자열 'merge'를 반환합니다.
입력 예시
a = "bacaa"
b = "abcaa"
출력
bacabcaaaa
설명: 문자열 'a'(“bacaa”)가 'b'(“abcaa”)보다 사전순으로 크므로, 먼저 'a'의 첫 문자인 'b'를 꺼냅니다. 이후 매 단계마다 남은 문자열끼리 비교하여 더 큰 쪽에서 문자를 하나씩 가져오면, 최종적으로 “bacabcaaaa”가 만들어집니다.
문제 해결 접근 방법
이 문제는 재귀(recursion)를 이용해 해결할 수 있습니다. 핵심 아이디어는 각 단계에서 문자열 'a'와 'b'의 남은 부분을 비교하여, 사전순으로 더 큰 문자열의 첫 문자를 'merge'에 붙이고 나머지 부분에 대해 함수를 다시 호출하는 것입니다.
여기서 중요한 점은 단일 문자만 비교하는 것이 아니라, 해당 위치 이후의 부분 문자열(substring) 전체를 비교해야 한다는 것입니다. 이렇게 해야 어느 쪽에서 문자를 가져오는 것이 전체적으로 더 큰 결과를 만드는지 정확하게 판단할 수 있습니다.
알고리즘 단계
- 두 입력 문자열 'a'와 'b'를 받습니다.
- 재귀 함수 concatenateLargest(string a, string b)는 두 문자열을 입력으로 받아 병합 결과인 가장 큰 문자열을 반환합니다.
- 두 문자열 중 하나라도 비어 있다면, 남은 문자열을 그대로 이어 붙여 반환합니다. 즉, (a + b)를 반환합니다.
- 문자열 'a'가 'b'보다 작거나 같으면, 'b'의 첫 문자를 결과에 붙이고 'b'의 나머지 부분으로 함수를 재귀 호출합니다.
- 그렇지 않고 'a'가 더 크다면, 'a'의 첫 문자를 결과에 붙이고 'a'의 나머지 부분으로 함수를 재귀 호출합니다.
- 재귀 호출이 모두 끝나면 완성된 병합 문자열을 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
string concatenateLargest(string a, string b) {
if (a.size() == 0 or b.size() == 0) {
return (a + b);
}
if (a <= b)
return b[0] + concatenateLargest(a, b.substr(1));
else
return a[0] + concatenateLargest(a.substr(1), b);
}
int main() {
string a = "bacaa";
string b = "abcaa";
cout << concatenateLargest(a, b) << endl;
return 0;
}
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
출력 결과
bacabcaaaa
두 문자열 “bacaa”와 “abcaa”는 위 규칙에 따라 병합되면 “bacabcaaaa”가 됩니다. 이처럼 재귀와 부분 문자열 비교를 활용하면, 두 문자열을 합칠 때 얻을 수 있는 사전순 최대 문자열을 효율적으로 구할 수 있습니다.