Pythonで解く「最大スワップ」問題：1回の桁入れ替えで最大の数を作るアルゴリズム

問題の概要

非負整数が与えられたとき、2つの桁を高々1回だけ入れ替えることで作れる最大の数を求めます。例えば、入力が 2736 の場合、出力は 7236 になります。これは先頭の「2」と次の「7」を入れ替えた結果です。

アルゴリズムの考え方

基本となるアイデアはシンプルです。元の数の各桁を降順に並べ替えたものが理論上の最大形になります。そこで、降順ソートした配列と元の配列を左から順に比較し、初めて一致しなくなった位置を見つけます。その位置にある小さい桁を、後続の桁の中で同じ大きい数字の最も右側（最下位）の出現箇所と入れ替えることで、数値を最大化できます。できるだけ下位の桁と交換するのがポイントで、これにより入れ替えによる増分が最大になります。

解法の手順

• num：数値を各桁に分解し、リスト化します
• num1：num を降順にソートします
• index を 0 で初期化します
• index が num の長さ未満である間、以下を繰り返します
  • num1[index] と num[index] が異なる場合
    • a := num の index+1 以降の部分配列
    • a を反転させます
    • a := len(a) − a.index(num1[index]) + index + 1 − 1（大きい数字の最も右側の位置を算出）
    • num[index] と num[a] を入れ替えます
    • ループを抜けます
  • index を 1 増やします
• num の各桁を連結して整数に変換します
• 結果を返します

Pythonでの実装例

以下の実装を見ると、処理の流れがより理解しやすくなります。

class Solution:
   def maximumSwap(self, num):
      num = list(map(int,list(str(num))))
      num1 = sorted(num,reverse=True)
      index=0
      while index<len(num):
         if num1[index]!=num[index]:
            a = num[index+1:]
            a.reverse()
            a=len(a) - a.index(num1[index])+index+1 -1
            num[index],num[a] = num[a],num[index]
            break
         index+=1
      return int("".join(str(x) for x in num))
ob1 = Solution()
print(ob1.maximumSwap(5397))

入力

5397

出力

9357

この例では、先頭付近の「5」と最大の「9」を入れ替えることで、5397 → 9357 という最大値が得られます。

計算量について

この手法では降順ソートを行うため、時間計算量は O(n log n)、桁を保持するリストの分だけ空間計算量は O(n) となります。なお、各数字の最後の出現位置をあらかじめ記録しておく方式を使えば、O(n) 時間で解くことも可能です。