Pythonで最大k回の隣接スワップ後に得られる最小の整数を求めるプログラム

非常に大きな整数を表す文字列 num と、整数 k が与えられているとします。隣接する2つの桁を入れ替える操作を最大 k 回まで行えるとき、実現できる最小の値を求める必要があります。

たとえば、入力が num = "5432"、k = 4 の場合、出力は 2453 になります。最初の数は 5432 ですが、1回目の交換で 4532、続いて 4523、次に 4253、そして最終的に 2453 となります。

アルゴリズムの考え方

この問題は貪欲法（グリーディ法）で効率的に解けます。左端の桁から順に、「残りの交換回数 k で移動できる範囲内に存在する最も小さい数字」をその位置へ引き寄せます。これを繰り返すことで、上位の桁から順にできるだけ小さな数字を配置し、全体として最小の整数を作り上げます。

解決手順

• min_num := num の各桁を昇順にソートした文字列
• i := 0、to_find := 0 で初期化
• num が min_num と等しくなく、k > 0 かつ i < num の長さである間、以下を繰り返す
  • indx := インデックス i 以降で to_find が出現する位置
  • indx が -1 でない間、以下を繰り返す
    • indx − i ≤ k の場合：
      • num := num[0〜i−1] + num[indx] + num[i〜indx−1] + num[indx+1〜末尾]
      • k := k − (indx − i)
      • i := i + 1
      • to_find := 0
      • indx を再び検索
    • それ以外の場合はループを抜ける
  • to_find := to_find + 1
• num を返す

実装例

理解を深めるために、以下のPython実装を見てみましょう。

def solve(num, k):
    min_num = sorted(list(num))
    min_num = ''.join(min_num)
    i = 0
    to_find = 0
    while num != min_num and k > 0 and i < len(num):
        indx = num.find(str(to_find), i)
        while indx != -1:
            if indx - i <= k:
                num = num[:i] + num[indx] + num[i:indx] + num[indx+1:]
                k -= (indx - i)
                i += 1
                to_find = 0
                indx = num.find(str(to_find), i)
            else:
                break
        to_find += 1
    return num

num = "5432"
k = 4
print(solve(num, k))

入力

"5432", 4

出力

2453

計算量

最悪の場合、各桁の配置ごとに文字列内の検索と再構築が必要になるため、時間計算量は O(n²) 程度になります（n は num の桁数）。必要な作業用変数以外に追加のデータ構造を持たないため、空間計算量は O(n) です。