C++でスワップ操作を1回だけ使って作れる最大の小さい数

このチュートリアルでは、与えられた数値 n より小さくなるように、スワップ（入れ替え）操作を1回だけ行ったときに得られる最大の数を求めるプログラムをC++で作成します。

アルゴリズムの考え方

問題を解くための手順は以下の通りです。

• 数値 n を文字列として初期化します。
• 文字列の末尾から先頭に向かって走査し、「現在の桁が次の桁より大きい」最初のインデックスを見つけて変数に保存します。
• そのようなインデックスが見つかった時点でループを抜けます。
• 次に、文字列の末尾から上記のインデックスまでの範囲を走査します。
  • その範囲内で「上記インデックスの桁より小さく、かつ条件を満たす桁の中で最も大きい」桁のインデックスを探します。
• 見つかった2つのインデックスの桁を入れ替え、更新後の数値を返します。

なお、走査しても入れ替え対象となる桁が存在しない場合（元の数値がすでに昇順に並んでいる場合など）は、それ以上小さくできないため "-1" を返します。

実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
string getTheNumber(string str) {
    int length = str.length();
    int index = -1;
    // 末尾から走査し、直前の桁より小さい桁の位置を探す
    for (int i = length - 2; i >= 0; i--) {
        if (str[i] > str[i+1]) {
            index = i;
            break;
        }
    }
    int smallerDigitIndex = -1;
    // 入れ替え候補の中で、index の桁未満かつ最大の桁を探す
    for (int i = length - 1; i > index; i--) {
        if (str[i] < str[index]) {
            if (smallerDigitIndex == -1 || str[i] >= str[smallerDigitIndex]) {
                smallerDigitIndex = i;
            }
        }
    }
    if (index == -1) {
        return "-1";
    }
    if (smallerDigitIndex != -1) {
        swap(str[index], str[smallerDigitIndex]);
        return str;
    }
    return "-1";
}
int main() {
    string str = "54624";
    cout << getTheNumber(str) << endl;
    return 0;
}

出力結果

上記のコードを実行すると、次の結果が得られます。

54426

この例では、入力 "54624" に対して「6」と「2」を入れ替えることで、1回のスワップで作れる最小の数 "54426" が得られています。この中で、1回のスワップで到達できる数の中で最大のものが選ばれている点に注目してください。

まとめ

この記事では、C++を使って、1回のスワップ操作で作成可能な「nより小さい最大の数」を求める方法を解説しました。文字列として桁を扱い、効率的に走査することで O(n) の計算量で解くことができます。このチュートリアルについて質問がある場合は、コメント欄でお知らせください。