C++で最大K回のスワップにより作成できる最大の数を求める方法

この問題では、2つの整数値 n と k が与えられ、最大K回までのスワップ（入れ替え）によって作成できる最大の数 を求めることが課題となります。

問題の概要

ここで必要なのは、与えられた数字の桁を最大k回まで入れ替えたときに作れる、最も大きな数を計算することです。

例で理解してみましょう

• 入力： n = 538, k = 1
• 出力： 835

説明： 「8」と「5」を入れ替えることで、最大の数「835」が得られます。

解法アプローチ

この問題を解くには、数字の桁を最大k回入れ替えながら、その都度できる数が最大であるかどうかを確認する必要があります。

基本的な考え方は以下の通りです。

1. 数の中から最大の桁を見つけます。
2. その最大の桁を先頭のインデックスと入れ替えます。
3. 同様の手順を、残りのk回分の入れ替えに対して繰り返します。

この処理は再帰的に実装すると、すべての組み合わせを網羅的に探索でき、確実に最大値を見つけられます。

解法の動作を示すプログラム

サンプルコード

#include <bits/stdc++.h>
using namespace std;

void calcMaxNumAfterSwap(string number, int k, string& maxString, int n){
    
    if (k == 0)
        return;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (number[i] < number[j]) {
                swap(number[i], number[j]);
                if (number.compare(maxString) > 0)
                    maxString = number;
                calcMaxNumAfterSwap(number, k - 1, maxString, n);
                swap(number[i], number[j]);
            }
        }
    }
}

int main(){
    
    string str = "15263";
    int k = 3;
    int size = str.length();
    string maxString = str;
    calcMaxNumAfterSwap(str, k, maxString, size);
    cout<<"The maximum number created after "<<k<<" swaps is "<<maxString;

    return 0;
}

出力

The maximum number created after 3 swaps is 65321

コードの解説

このプログラムでは、関数 calcMaxNumAfterSwap が再帰的に呼び出され、可能なすべての桁の入れ替えパターンを試します。各ステップで現在の数がこれまでの最大値 maxString より大きければ、それを新しい最大値として記録します。バックトラッキングのために、再帰呼び出しの後に入れ替えを元に戻している点がポイントです。

上記の例では、文字列「15263」に対して3回のスワップを行うことで、最大の数「65321」が作成されます。