【C++】最大1回のスワップ操作で作れる最大の数を求める方法

この問題では、正の整数が1つ与えられます。求められているのは、最大で1回のスワップ(桁の入れ替え)操作を使って、可能な限り大きな数を作り出すプログラムを書くことです。

新しい数は、元の数を構成する桁を並べ替えて作成します。ただし、入れ替えてよいのは1箇所のみです。

問題を理解するための例

入力: n = 63512
出力: 65312

上の例では、2桁目の「3」と3桁目の「5」を入れ替えることで、65312という最大の数が得られます。

解法アプローチ1:すべてのスワップを試す方法

最もシンプルな方法は、与えられた数の桁のペアを入れ替えることで作れるすべての数を列挙し、その中から最大のものを返すというものです。数値をいったん文字列に変換し、各ペアの位置を実際に入れ替えながら大小を比較していきます。

この方法は実装が簡単な反面、桁のペアごとに数値への変換と比較が必要となるため、桁数が増えると計算量が大きくなります(時間計算量は O(n³) 程度)。

サンプルコード

#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

792156 の場合、2桁目の「9」と3桁目の「2」を入れ替えることで、972156 という最大の数が得られています。

解法アプローチ2:最適なスワップを直接見つける効率的な方法

より効率的なアプローチは、結果を最大化するスワップを1つだけ特定することです。具体的には、数値を右から左へ走査し、それまでに見た中で最大の桁とその位置を記録していきます。走査中に「記録した最大桁より小さい桁」が見つかったら、その位置が入れ替え候補(左側)となり、記録中の最大桁の位置が入れ替え相手(右側)となります。

最終的に得られた2つの位置を入れ替えることで最大の数が完成します。また、左側のどの桁も右側の最大桁より小さくなければ(数が降順に並んでいれば)、1回のスワップで数を大きくすることはできないため、元の数をそのまま返します。

この方法は数を一度走査するだけでよいため、時間計算量 O(n) で動作し、桁数が多い場合でも高速に処理できます。

サンプルコード

#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

まとめ

「最大1回のスワップで最大の数を作る」問題は、すべての入れ替えを試す O(n³) の単純な方法でも解けますが、右から左へ走査して最適な交換位置を見つける O(n) のアプローチの方がはるかに効率的です。実務や競技プログラミングなど制約が厳しい場面では、後者の手法を採用することをおすすめします。