C++で数値リストを並べ替えて最大の数を作成するプログラム

問題の概要

nums という数値のリストが与えられたとき、その順序を並べ替えて、可能な限り最大の数を作成し、文字列として返すことを考えます。

例えば、nums = [20, 8, 85, 316] の場合、出力は "88531620" となります。

解決のアプローチ

この問題を解くためには、以下の手順に従います。

• 配列 temp を定義します
• nums の各要素 i に対して、文字列に変換して temp に挿入します
• temp を辞書順に基づいてソートします(2つの文字列 a, b を比較する際、「a + b」が「b + a」より大きいかどうかを判定します)
• temp の各文字列 s を順番に res に連結します
• res を返します

比較関数のポイント

このアルゴリズムの核心は比較関数 cmp にあります。単純に文字列を辞書順で比較するだけでは、例えば "3" と "30" のようなケースで正しい結果が得られません。そこで、2つの文字列を連結した結果の大小を比較することで、「どちらの順序で並べた方が大きな数になるか」を正しく判定できます。例えば "3" と "30" の場合、"330" は "303" より大きいため、"3" を先に配置するのが正解です。

実装例

以下の実装を見ると、より理解が深まります。

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

static bool cmp(string a, string b) {
    return (a + b) >= (b + a);
}
string solve(vector<int>& nums) {
    vector<string> temp;
    for (int i : nums) {
        temp.push_back(to_string(i));
    }
    sort(temp.begin(), temp.end(), cmp);
    string res;
    for (string s : temp) {
        res += s;
    }
    return res;
}

int main(){
    vector<int> v = {20, 8, 85, 316};
    cout << solve(v);
}

入力

{20, 8, 85, 316}

出力

88531620

まとめ

このように、数値を文字列に変換してから連結結果で比較してソートすることで、リストの並べ替えによって作れる最大の数を効率よく求めることができます。計算量はソートに依存し、O(n log n) で処理できるため、要素数が多い場合でも実用的です。