K번 자리 교환으로 만들 수 있는 최댓값 구하기 (백트래킹 알고리즘)

이 문제에서는 하나의 양의 정수 문자열이 주어지며, 자릿수를 최대 K번 서로 교환(swap)하여 만들 수 있는 값이 가장 큰 순열을 찾아야 합니다.

이 문제는 백트래킹(backtracking) 기법을 활용하여 해결할 수 있습니다. 특정 자릿수를 선택한 뒤, 그 뒤에 위치한 다른 자릿수들과 하나씩 교환해 보면서 더 큰 수를 탐색합니다. 이 과정을 K번 반복하는데, 교환 결과가 기존의 최댓값보다 작거나 같다면 이전 상태로 되돌아가(백트래킹) 다른 경우를 다시 시도하는 방식으로 동작합니다.

입력 및 출력

입력:
여러 자릿수로 이루어진 정수
입력값: 129814999
출력:
자릿수 교환을 통해 만들 수 있는 최댓값
출력값: 999984211

알고리즘

maxNum(number, swaps, maxNumber)

입력 − 숫자 문자열(number), 허용된 교환 횟수(swaps), 현재까지의 최댓값 문자열(maxNumber)

출력 − maxNumber를 갱신하여 가장 큰 값을 얻습니다.

Begin
    if swaps = 0, then
        return
    n := 숫자의 자릿수
    for i := 0 to n-2, do
        for j := i+1 to n-1, do
            if number[i] < number[j], then
                number[i]와 number[j]를 교환
                if number가 maxNumber보다 크면, then
                    maxNumber := number
                maxNum(number, swaps-1, maxNumber)  // 재귀 호출
                백트래킹을 위해 number[i]와 number[j]를 다시 원래대로 교환
        done
    done
End

구현 예제 (C++)

#include <iostream>
using namespace std;

void maxNum(string str, int swaps, string &max) {
    if(swaps == 0)          // 남은 교환 횟수가 없으면 종료
        return;
    int n = str.length();

    for (int i = 0; i < n - 1; i++) {       // 각 자릿수에 대해
        for (int j = i + 1; j < n; j++) {
            if (str[i] < str[j]) {          // 앞 자릿수가 뒤 자릿수보다 작은 경우
                swap(str[i], str[j]);
                if (str.compare(max) > 0)   // 현재 수가 더 크면 최댓값 갱신
                    max = str;
                maxNum(str, swaps - 1, max); // 다음 교환 진행
                swap(str[i], str[j]);        // 실패 시 교환을 되돌림 (백트래킹)
            }
        }
    }
}

int main() {
    string str = "129814999";
    int swapNumber = 4;
    string max = str;
    maxNum(str, swapNumber, max);
    cout << "주어진 숫자: " << str << endl;
    cout << "최댓값: " << max << endl;
}

실행 결과

주어진 숫자: 129814999
최댓값: 999984211

위 코드에서 swapNumber가 4로 설정된 것에 주목할 필요가 있습니다. 즉, 최대 4번의 자리 교환만으로도 129814999를 999984211로 변환할 수 있다는 의미입니다. 재귀 호출을 통해 모든 가능한 교환 조합을 탐색하되, 매 단계마다 현재까지 발견된 최댓값과 비교하여 더 나은 결과를 유지하기 때문에 최종적으로 전역 최적해(global optimum)를 보장할 수 있습니다.