【C++】最大1回のスワップ操作で最小の数を作る方法を解説

問題概要

この問題では、正の整数が1つ与えられます。求められているのは、最大でも1回のスワップ（桁の入れ替え）操作を使って、その数字の桁から作れる最小の数を作るプログラムです。

つまり、既存の数の桁を使って新しい数を作りますが、許されるのは元の数からの1箇所だけの入れ替えです。

例で問題を確認しよう

入力：n = 63519
出力：36519

この例では、先頭の「6」と2番目の「3」を入れ替えることで、63519 より小さい 36519 を作れています。

解法アプローチ①：すべてのスワップを試す（全探索）

最もシンプルな方法は、与えられた数の桁のペアを入れ替えて作られるすべての数を列挙し、その中で最小のものを返すというものです。具体的には、数を文字列に変換し、すべての位置の組み合わせについて実際に入れ替えを行いながら結果を比較していきます。

この方法は実装が非常に簡単ですが、計算量は O(n³) 程度になるため、桁数が多い場合には非効率になる点に注意が必要です。

サンプルコード

#include <iostream>
using namespace std;

int findSmallestNumSwapDig(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<<"元の数： "<<num<<endl;
    cout<<"1回のスワップで作れる最小の数： "<<findSmallestNumSwapDig(num) << endl;
    return 0;
}

出力

元の数： 792156
1回のスワップで作れる最小の数： 192756

解法アプローチ②：補助配列を使った効率的な方法

もう一つのアプローチは、補助配列 aux[] を活用する方法です。この配列には、各インデックス i よりも右側（より大きいインデックス側）にある最小の桁のインデックスを格納します。該当する桁が存在しない場合は -1 で初期化しておきます。

処理の流れは以下の通りです。

• 数を右から左へ走査しながら、aux[] 配列を構築する。
• 先頭の桁については、入れ替え先として0以外の最小の桁を探す（先頭が0になると桁数が変わり、意図した結果にならないため）。先頭より小さい0以外の桁が存在すれば、それと入れ替える。
• 先頭の入れ替えができない場合は、aux[] を参照して、右側により小さい桁を持つ最初の位置 i を見つけ、arr[i] と arr[aux[i]] を入れ替えて結果を返す。

この方法なら、全体の計算量を O(n) に抑えることができ、桁数が多くても高速に動作します。

サンプルコード

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

int findSmallestNumSwapDig(int N){

    string num = to_string(N);
    int n = num.size();
    int auxArr[n], right;
    auxArr[n - 1] = -1;
    right = n - 1;
    for (int i = n - 2; i >= 1; i--) {
        if (num[i] >= num[right])
            auxArr[i] = right;
        else {
            if (num[i] == num[i + 1])
                auxArr[i] = right;
            else {
                auxArr[i] = -1;
                right = i;
            }
        }
    }
    int small = -1;
    for (int i = 1; i < n; i++)
    if (num[i] != '0') {
        if (small == -1) {
            if (num[i] < num[0])
                small = i;
        }
        else if (num[i] <= num[small])
            small = i;
    }
    if (small != -1)
        swap(num[0], num[small]);
    else {
        for (int i = 1; i < n; i++) {
            if (auxArr[i] != -1 && num[i] != num[auxArr[i]]) {
                swap(num[i], num[auxArr[i]]);
                break;
            }
        }
    }
    return stoi(num);
}
int main(){
    int num = 792156;
    cout<<"元の数： "<<num<<endl;
    cout<<"1回のスワップで作れる最小の数： "<<findSmallestNumSwapDig(num)<< endl;
    return 0;
}

出力

元の数： 792156
1回のスワップで作れる最小の数： 192756

まとめ

C++で「最大1回のスワップで最小の数を作る」問題には、大きく分けて2つの解き方があります。実装が簡単な全探索方式は O(n³)、補助配列を使った方式は O(n) と効率的です。技術面接や競技プログラミングでは、制約条件に応じて適切な手法を選択できることが重要なので、両方のアプローチを理解しておくとよいでしょう。