C++で配列の数字から作れる最大の数を求める方法

数字の配列が与えられたとき、その配列に含まれるすべての数字を使って作れる最大の数を求める問題を考えてみましょう。

例えば、配列が [3, 3, 9, 6, 2, 5] の場合、これらの数字を組み合わせて作れる最大の数は 965332 になります。

アプローチの考え方

この問題に対する最も直感的な解法は、配列内の数字を降順（非増加順）にソートして、その順に出力することです。ソートを使えば確かに正しい答えが得られますが、計算量は O(n log n) となります。

しかし、より効率的な方法があります。それがカウントソート（頻度カウント）の考え方を応用する手法です。

具体的には、次の手順で処理を行います。

1. サイズ10の配列を作成し、各数字（0〜9）の出現回数を記録します。
2. 9から0に向かって順番に、記録された回数だけ数字を出力していきます。

この方法なら O(n + k)（kは数字の種類数）で処理でき、ソートよりも高速に動作します。

サンプルコード

#include <iostream>
#include <string>
using namespace std;
int maxNumFromNum(int arr[], int n) {
    int freq[10] = {0};
    for (int i=0; i<n; i++)
    freq[arr[i]]++;
    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 digits[] = {3, 3, 9, 6, 2, 5};
    int n = sizeof(digits)/sizeof(digits[0]);
    cout << "Maximum number: " << maxNumFromNum(digits, n);
}

実行結果

Maximum number: 965332

コードの解説

このプログラムのポイントは以下の通りです。

• freq 配列： 各数字の出現回数を格納します。例えば入力に「3」が2つ含まれていれば、freq[3] は 2 になります。
• res と mul： 結果の数値を組み立てるために使用します。mul を10倍ずつ増やしながら、大きい数字から順に上位の桁へ配置していきます。
• ループの順序： 9から0へ向かって処理することで、大きな数字が自然と左側（上位の桁）に配置され、最大の数が完成します。

なお、結果を整数型（int）で返しているため、桁数が非常に多い場合はオーバーフローに注意が必要です。そのようなケースでは long long 型や文字列として扱う方法を検討するとよいでしょう。