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

このチュートリアルでは、数字を1回だけ入れ替える（スワップ）ことで作れる最大の数を求めるプログラムをC++で作成します。

アルゴリズムの手順

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

• 数値nを初期化します。
• 整数を文字列に変換します。
• 文字列の末尾から先頭に向かって走査するループを作成します。
  • それまでに見つかった最大の桁とそのインデックスを記録します。
  • 現在の桁が記録中の最大桁より小さい場合は、開始インデックスを現在のインデックスに、終了インデックスを最大桁のインデックスに更新します。
• ループ終了後に開始インデックスが-1のままなら、入れ替えは不要なのでnをそのまま返します。
• それ以外の場合は、開始インデックスと終了インデックスの桁を入れ替えます。
• 文字列を整数に変換して返します。

実装例

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

#include <bits/stdc++.h>
using namespace std;
int getLargestNumber(int n) {
   int maxDigit = -1;
   int maxDigitIndex = -1;
   int startIndex = -1;
   int endIndex = -1;
   string nInStr = to_string(n);
   for (int i = nInStr.size() - 1; i >= 0; i--) {
      if (nInStr[i] > maxDigit) {
         maxDigit = nInStr[i];
         maxDigitIndex = i;
         continue;
      }
      if (nInStr[i] < maxDigit) {
         startIndex = i;
         endIndex = maxDigitIndex;
      }
   }
   if (startIndex == -1) {
      return n;
   }
   swap(nInStr[startIndex], nInStr[endIndex]);
   return stoi(nInStr);
}
int main() {
   int n = 678;
   cout << getLargestNumber(n) << endl;
   return 0;
}

出力

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

876

まとめ

このアルゴリズムでは、文字列を後ろから走査することで「右側に存在する最大の桁」を記録し、それより左にあるより小さい桁と入れ替えることで、1回のスワップで最大の数を効率的に求められます。計算量は桁数をdとするとO(d)となり、非常に効率的です。なお、数字がすでに降順に並んでいる場合は入れ替えが発生しないため、元の数値がそのまま返されます。

このチュートリアルについて質問がある場合は、コメント欄でお知らせください。