与えられた数値を並べ替えて最大の数を作る方法｜C++での実装例

この記事では、与えられた複数の数値を並べ替えて、可能な限り大きな数を作る方法を解説します。例えば、{45, 74, 23} という3つの数値が与えられた場合、プログラムは最大の数「744523」を出力します。ここで重要なのは、各桁の数字をバラバラに並べ替えるのではなく、数値そのものをひとまとまりの単位として配置するという点です。

この問題を解くには、数値を文字列として扱い、ソートを行います。ただし、通常の大小比較とは異なる独自の比較ロジックを使用します。比較関数は2つの数値 a と b を受け取り、それぞれを連結した「ab」と「ba」を生成し、どちらが大きいかを判定します。大きい方の組み合わせが先に来るように並べることで、全体として最大の数が得られます。

例えば「45」と「74」を比較する場合、「4574」と「7445」を作り、大きい方である「7445」を採用するため、「74」が先に並びます。

アルゴリズム

compareStrings(a, b)

begin
    ab := a に b を連結した文字列
    ba := b に a を連結した文字列
    ba と ab を比較し、ba の方が大きければ 1 を返す。そうでなければ 0 を返す
end

getLargest(arr)

begin
    compareStrings() を比較関数として使い、arr をソートする
    arr 内の各文字列 s に対して以下を実行する
        s を出力する
    繰り返し終了
end

C++による実装例

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int stringCompare(string a, string b) {
    string ab = a + b;
    string ba = b + a;
    return ab.compare(ba) > 0 ? 1 : 0;
}

void getLargest(vector<string> arr) {
    sort(arr.begin(), arr.end(), stringCompare); // 配列をソート
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i];
}

int main() {
    vector<string> arr;
    arr.push_back("45");
    arr.push_back("74");
    arr.push_back("23");
    getLargest(arr);
}

出力結果

744523

解説

この比較ロジックのポイントは、連結した結果そのものを比較することで、桁数が異なる数値同士でも正しい順序を決定できる点にあります。単純に数値の大小や辞書順で比較すると、意図しない順序になってしまうことがありますが、連結結果を比較する方式なら、例えば「3」と「30」の場合も「330」と「303」を比べて正しく判断でき、常に最大の数を構成できます。