두 개의 문자열 'a'와 'b'와 문자열 'merge'가 있다고 가정해 보겠습니다. 작업은 다음과 같은 방식으로 'a'와 'b'의 문자로 'merge' 문자열을 채우는 것입니다.
- 'a' 문자열이 비어 있지 않은 경우 'a' 문자열에서 첫 번째 문자를 제거하고 'merge' 문자열에 복사합니다.
- 'b' 문자열이 비어 있지 않은 경우 'b' 문자열에서 첫 번째 문자를 제거하고 'merge' 문자열에 복사합니다.
- 문자열 'a' 및 'b'가 비어 있지 않은 경우 문자열 'a'에서 첫 번째 문자를 제거하고 이를 문자열 'merge'로 복사한 다음 문자열 'b에서 첫 번째 문자(있는 경우)를 제거합니다. '를 입력하고 'merge' 문자열에 복사합니다.
- 사전순으로 두 문자열에서 문자를 제거합니다. 즉, 문자열 'a'가 문자열 'b'보다 크면 문자열 'a'에서 문자를 제거한 다음 문자열 'b'에서 제거합니다.
- '병합' 문자열을 반환합니다.
예를 들어
입력-1:
a = “bacaa”b = “abcaa”
출력:
babcacaaaa
설명:
주어진 문자열 'a'는 사전순으로 문자열 'b'보다 크므로 문자열 'a', 즉 "b"에서 첫 번째 문자를 추출한 다음 문자열 'b'에서 추출합니다. 추출 후 문자열은 "babcacaaaa"가 됩니다.
이 문제를 해결하기 위한 접근 방식
이 문제를 해결하기 위한 재귀적 접근 방식은 문자열 'a'와 문자열 'b'의 각 문자를 추출하고 문자열 'a'의 문자가 사전순으로 다른 문자열보다 큰지 확인하고 마지막으로 문자열 'merge'에 연결하는 것입니다. .
여러 위치 뒤에 있는 각 문자의 하위 문자열을 찾고 사전순으로 다른 문자열보다 큰 경우 '병합'으로 연결합니다.
- 두 개의 입력 문자열 'a'와 'b'를 사용합니다.
- 재귀 문자열 함수 concatenateLargest(문자열 a, 문자열 b)는 두 개의 문자열을 입력으로 사용하고 연결 후 가장 큰 문자열, 즉 (문자열 'a' + 문자열 'b')를 반환합니다.
- 두 문자열이 모두 비어 있으면 문자열 'a' + 문자열 'b'를 반환합니다.
- 문자열 'a'가 문자열 'b'보다 작거나 같으면 첫 번째 문자를 추출하고 다른 문자에 대해 재귀적으로 함수를 호출합니다.
- 문자열 'b'가 문자열 'b'보다 작거나 같으면 첫 번째 문자를 추출하고 다른 문자에 대해 재귀적으로 함수를 호출합니다.
- 연결된 문자열을 반환합니다.
예시
#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"가 됩니다.