C++である整数の各桁を並べ替えて作れる最大の数を求めるアルゴリズム

問題概要

n桁の整数が与えられたとき、その数を構成するすべての桁の数字を使って作成できる最大の数を求めることを考えます。例えば、与えられた数が 339625 の場合、各桁を並べ替えることで作れる最大の数は 965332 となります。

解決のアプローチ

この問題は、各桁の数字を降順（非増加順）にソートして出力するだけで簡単に解くことができます。しかし、ここではさらに効率的な方法を紹介します。

具体的には、サイズ10の配列を用意して各数字（0〜9）の出現頻度を記録します。その後、9から0へと順番に走査しながら、出現回数に応じて数字を配置していくことで、最大の数を効率よく構築できます。この手法の時間計算量は O(n) となり、一般的なソートアルゴリズムの O(n log n) よりも高速に動作します。

C++での実装例

#include <iostream>
#include <string>
using namespace std;
int maxNumFromNum(int num) {
    int freq[10] = {0};
    string str = to_string(num);
    for (int i = 0; i < str.length(); i++)
        freq[str[i] - '0']++;
    int res = 0, mul = 1;
    for (int i = 0; i <= 9; i++) {
        while (freq[i] > 0) {
            res = res + (i * mul);
            freq[i]--;
            mul = mul * 10;
        }
    }
    return res;
}
int main() {
    int num = 339625;
    cout << "Maximum number: " << maxNumFromNum(num);
}

コードのポイント

• freq 配列： 各数字（0〜9）の出現回数をカウントします。
• res と mul： 小さい数字から順に加算し、mul を10倍ずつ増やすことで、大きい数字が自然と上位の桁に配置される仕組みです。
• 計算量： 桁数を n とすると、時間計算量は O(n)、空間計算量は固定サイズの配列のみ使用するため O(1) です。

実行結果

Maximum number: 965332

まとめ

このように、度数分布配列（バケット）を活用することで、桁の並べ替えによる最大数の生成を線形時間で効率的に求められます。桁数が多い場合や同じ処理を繰り返し実行するケースで特に有効なテクニックなので、ぜひ覚えておきましょう。