C++로 딱 한 번의 스왑만 사용해 만들 수 있는 가장 큰 숫자 구하기

이 문제에서는 양의 정수가 하나 주어집니다. 우리의 과제는 최대 한 번의 자릿수 교환(swap) 연산만을 사용하여 만들 수 있는 가장 큰 숫자를 구하는 프로그램을 작성하는 것입니다.

즉, 기존 숫자의 자릿수들을 이용해 새로운 숫자를 만들되, 단 한 쌍의 자릿수만 서로 바꿀 수 있습니다.

문제 이해를 위한 예시

입력: n = 63512
출력: 65312

63512에서 첫 번째 자리의 '3'과 두 번째 자리의 '5'를 교환하면 65312가 되며, 이것이 한 번의 스왑으로 만들 수 있는 가장 큰 숫자입니다.

방법 1: 모든 스왑 경우를 탐색하는 브루트 포스

가장 직관적인 해결 방법은 주어진 숫자의 자릿수 쌍들을 모두 교환해 보면서 생성할 수 있는 모든 숫자를 확인하는 것입니다. 그중 가장 큰 값을 결과로 반환하면 됩니다.

이를 위해 숫자를 문자열로 변환한 뒤, 각 위치의 자릿수를 서로 바꿔가며 비교합니다.

구현 예제

#include <iostream>
using namespace std;

int findLargestNumSwapDig(int N){

    string strNum = to_string(N);
    string temp = strNum;
    for (int i = 0; i < strNum.size(); i++) {
        for (int j = i + 1; j < strNum.size(); j++) {
            swap(strNum[i], strNum[j]);
            if (stoi(strNum) > stoi(temp))
                temp = strNum;
            swap(strNum[i], strNum[j]);
        }
    }
    return stoi(temp);
}
int main(){
    int num = 792156;
    cout<<"The number is "<<num<<endl;
    cout<<"The largest number created by swapping one digit is "<<findLargestNumSwapDig(num) << endl;
    return 0;
}

실행 결과

The number is 792156
The largest number created by swapping one digit is 972156

이 방법은 모든 자릿수 쌍을 두 번 중첩 반복문으로 검사하므로 시간 복잡도는 O(n²)입니다. 자릿수 개수가 많아지면 비효율적일 수 있지만, 로직이 단순하고 이해하기 쉽다는 장점이 있습니다.

방법 2: 오른쪽부터 스캔하는 그리디 접근법

더 효율적인 방법은 어떤 스왑이 가장 큰 숫자를 만드는지를 직접 찾아내는 것입니다.

핵심 아이디어는 다음과 같습니다. 숫자를 오른쪽에서 왼쪽으로 스캔하면서 지금까지 등장한 최댓값 자릿수와 그 위치를 기록합니다. 현재 자릿수가 기록된 최댓값보다 작다면, 그 위치(왼쪽 인덱스)와 최댓값의 위치(오른쪽 인덱스)를 교환 후보로 저장합니다. 스캔이 끝난 뒤 저장된 후보 쌍을 실제로 교환하면 가장 큰 숫자를 얻을 수 있습니다.

주의할 점은 같은 값의 자릿수가 여러 개 있을 때 가장 오른쪽에 있는 최댓값과 교환해야 한다는 것입니다. 그래야 더 작은 자릿값(10의 거듭제곱이 작은 자리)을 큰 값으로 바꾸게 되어 결과가 최대가 됩니다.

구현 예제

#include <iostream>
using namespace std;

int findLargestNumSwapDig(int N){

    int currMaxDig = -1;
    int currMaxInd = -1;
    int lSwap = -1;
    int rSwap = -1;

    string strNum = to_string(N);
    for (int i = strNum.size() - 1; i >= 0; i--) {

        if (strNum[i] > currMaxDig) {
            currMaxDig = strNum[i];
            currMaxInd = i;
            continue;
        }
        if (strNum[i] < currMaxDig) {
            lSwap = i;
            rSwap = currMaxInd;
        }
    }
    if (lSwap == -1)
        return N;
    swap(strNum[lSwap], strNum[rSwap]);
    return stoi(strNum);
}
int main(){
    int num = 792156;
    cout<<"The number is "<<num<<endl;
    cout<<"The largest number created by swapping one digit is "<<findLargestNumSwapDig(num) << endl;
    return 0;
}

실행 결과

The number is 792156
The largest number created by swapping one digit is 972156

이 방법은 숫자를 한 번만 스캔하면 되므로 시간 복잡도가 O(n)으로, 브루트 포스 방식보다 훨씬 효율적입니다. 또한 이미 내림차순으로 정렬된 숫자처럼 어떤 스왑도 이득이 되지 않는 경우에는 원래 숫자를 그대로 반환합니다.