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

JavaScriptで、数値を第1引数（唯一の引数）として受け取り、その数値の任意の2桁を最大1回だけ入れ替えたときに作れる最大の数を返す関数を実装します。すでにその数が可能な最大値である場合は、元の数をそのまま返します。

問題の例

入力が 1625 の場合を考えてみましょう。先頭の「1」と「6」を入れ替えることで 6125 が得られます。これが1回のスワップで作れる最大の数です。

const num = 1625;
// 出力: 6125

解決策：貪欲法によるアプローチ

この問題は貪欲法（Greedy法）を使うことで効率的に解けます。基本的な手順は以下のとおりです。

1. 数値を左から順に走査します。
2. 各位置において、その位置より右側にある最大の数字（同じ数字が複数ある場合は最も右側のもの）を探します。
3. 右側の最大の数字が現在の位置の数字よりも大きければ、両者を入れ替えて処理を終了します。
4. より大きい数字が存在しない場合は、そのまま次の位置へ進みます。

ここで注意したいのは、必ずしも数値全体の最大桁と交換すればよいわけではないという点です。たとえば 9618 の場合、全体の最大桁「9」はすでに先頭にあるため、「6」と「8」を入れ替えた 9816 が正解になります。

コード例

const makeOneSwap = (num = 1) => {
  const digits = String(num).split('');

  for (let i = 0; i < digits.length - 1; i++) {
    let maxDigit = digits[i];
    let maxIndex = i;

    // 現在位置より右側にある最大の数字と、その最も右の位置を探す
    for (let j = i + 1; j < digits.length; j++) {
      if (Number(digits[j]) >= Number(maxDigit)) {
        maxDigit = digits[j];
        maxIndex = j;
      }
    }

    // 右側にもっと大きい数字があれば入れ替えて終了
    if (Number(maxDigit) > Number(digits[i])) {
      [digits[i], digits[maxIndex]] = [digits[maxIndex], digits[i]];
      break;
    }
  }

  return Number(digits.join(''));
};

console.log(makeOneSwap(1625)); // 6125
console.log(makeOneSwap(9618)); // 9816
console.log(makeOneSwap(6125)); // 6521
console.log(makeOneSwap(9999)); // 9999（すでに最大なのでそのまま返る）

出力結果

コンソールには次のように表示されます。

6125
9816
6521
9999

計算量について

時間計算量は O(n²)、空間計算量は O(n) です（n は桁数）。桁数が少ない通常の数値であれば十分に高速に動作するため、実用上問題になることはほとんどありません。