C++에서 최대 K번 교환(Swap)으로 만들 수 있는 최댓값 찾기

문제 소개

이 문제에서는 두 개의 정수 n과 k가 주어지며, 우리의 목표는 최대 K번의 교환(swap)을 통해 만들 수 있는 최대 숫자를 찾는 것입니다.

문제 설명: 주어진 숫자의 자릿수를 최대 k번까지 서로 교환했을 때 얻을 수 있는 가장 큰 수를 계산해야 합니다.

예제를 통해 문제를 이해해 보겠습니다.

• 입력: n = 538, k = 1
• 출력: 835
• 설명: 8과 5의 위치를 서로 교환하면 됩니다.

해결 접근 방식

이 문제를 해결하려면 숫자의 자릿수를 k번 교환하면서 매 단계마다 결과가 최댓값인지 확인해야 합니다.

핵심 아이디어는 다음과 같습니다. 현재 위치보다 뒤쪽에 있는 자릿수 중에서 더 큰 값을 찾아 앞쪽 인덱스의 요소와 교환하고, 이 과정을 처음부터 k개의 인덱스에 대해 재귀적으로 반복합니다. 이처럼 모든 가능한 교환 조합을 탐색하는 백트래킹(backtracking) 기법을 활용하면, 주어진 교환 횟수 제한 안에서 만들 수 있는 최댓값을 반드시 찾을 수 있습니다.

솔루션 구현 예제

#include <bits/stdc++.h>
using namespace std;

void calcMaxNumAfterSwap(string number, int k, string& maxString, int n){
    
    if (k == 0)
        return;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (number[i] < number[j]) {
                swap(number[i], number[j]);
                if (number.compare(maxString) > 0)
                    maxString = number;
                calcMaxNumAfterSwap(number, k - 1, maxString, n);
                swap(number[i], number[j]);
            }
        }
    }
}

int main(){
    
    string str = "15263";
    int k = 3;
    int size = str.length();
    string maxString = str;
    calcMaxNumAfterSwap(str, k, maxString, size);
    cout<<"The maximum number created after "<<k<<" swaps is "<<maxString;

    return 0;
}

코드 동작 원리

• k == 0이면 교환 횟수를 모두 사용한 것이므로 재귀를 종료합니다.
• 이중 반복문을 통해 모든 자릿수 쌍 (i, j)을 검사합니다.
• number[i] < number[j]인 경우 두 자릿수를 교환하고, 현재 문자열이 지금까지의 최댓값(maxString)보다 크면 갱신합니다.
• 남은 교환 횟수(k - 1)로 재귀 호출을 진행한 뒤, 다음 경우의 수를 탐색하기 위해 자릿수를 원래대로 되돌리는 백트래킹을 수행합니다.

실행 결과

The maximum number created after 3 swaps is 65321