C++에서 B의 자릿수로 A의 일부 자릿수를 교체해 A의 값 최대화하기

문제 개요

이 문제의 목표는 숫자 A의 일부 자릿수를 다른 숫자 B에 포함된 자릿수로 교체하여 A의 값을 최대화하는 것입니다. 만약 A의 값을 더 이상 높일 수 없다면 어떤 자릿수도 교체하지 않습니다.

참고: B의 각 자릿수는 한 번만 사용할 수 있습니다.

예제를 통해 문제를 구체적으로 살펴보겠습니다.

입력

A = "1221"
B = "1211"

출력

A의 가능한 최댓값: 2221

설명: 여기서는 B에서 2를 선택해 A의 첫 번째 자리에 있는 1과 교체했습니다. A의 다른 자릿수를 2나 1로 바꾸더라도 값이 증가하지 않으므로 이것이 유일한 선택입니다.

입력

A = "1002"
B = "3200"

출력

A의 가능한 최댓값: 3202

접근 방식

이 문제는 그리디(Greedy) 기법으로 해결할 수 있으며, 아래 프로그램은 다음과 같은 단계로 동작합니다.

A의 각 자릿수가 B의 자릿수보다 작으면 해당 자릿수로 교체합니다.
먼저 문자열 B를 오름차순으로 정렬합니다.
A는 왼쪽부터 탐색을 시작합니다.
B는 오른쪽부터 탐색합니다.
A의 현재 자릿수보다 B의 자릿수가 더 크면 두 값을 교체한 뒤, A의 포인터는 앞으로 이동하고 B의 포인터는 뒤로 이동시킵니다.

B를 오름차순으로 정렬한 뒤 뒤쪽부터 사용하면 항상 남아 있는 숫자 중 가장 큰 값을 우선적으로 배치할 수 있고, 자릿값이 큰 왼쪽 자리부터 채워 나가기 때문에 전체 값을 가장 효율적으로 키울 수 있습니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
// a의 최대화된 값을 반환하는 함수
string valueup(string str1, string str2){
    // 자릿수를 오름차순으로 정렬
    sort(str2.begin(), str2.end());
    int len1 = str1.length();
    int len2 = str2.length();
    int j = len2 - 1;
    for (int i = 0; i < len1; i++) {
       // b의 모든 자릿수를 소진한 경우
       if (j < 0)
          break;
       if (str2[j] > str1[i]) {
          str1[i] = str2[j];
          j--; // 한 번 사용한 자릿수는 제외
       }
    }
    return str1;
}
// 드라이버 코드
int main(){
    string a = "1204";
    string b = "4521";
    cout << valueup(a, b);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.

복잡도 분석

정렬에 O(M log M)(M은 B의 길이), 탐색에 O(N)(N은 A의 길이)이 소요되므로 전체 시간 복잡도는 O(N + M log M)입니다.