【C++】偶数・奇数の順序を保ちながら並べ替えて作れる最大の数

問題の概要

この問題では、数値の配列が与えられ、それらを並べ替えることで作れる最大の数を求めます。ただし、並べ替えには重要な制約があります。それは「偶数同士の相対的な順序」と「奇数同士の相対的な順序」は、元の配列のまま変更してはならないというものです。

具体例を使って理解を深めましょう。

入力 : {17, 80, 99, 27, 14, 22}
出力 : 801799271422

偶数と奇数の順序 :
偶数 : 80 14 22
奇数 : 17 99 27

この例では、配列内で最も大きい数は99ですが、奇数の順序では17が先に現れるため、99を先頭に置くことはできません。そこで、まず偶数の先頭である80を選び、以降は偶数列と奇数列の先頭要素を順に比較しながら並べることで、80 17 99 27 14 22 という並びが得られます。

解き方のアプローチ

問題の本質が理解できたところで、解決策を考えてみましょう。ここでは、単純に降順ソートを行うことはできません。偶数と奇数の順序に関する制約があるためです。

そこで採用するのは、偶数列と奇数列を別々に管理しながら、それぞれの先頭要素を比較して大きい方を採用していくというマージ型の手法です。これにより、制約を守りつつ全体として最大の数を作れます。

アルゴリズム

ステップ1 : 偶数用と奇数用の2つのキュー(構造)を作成し、
          元の配列における順序を保持します。
ステップ2 : 各キューから先頭の要素を1つずつ取り出し、
          どちらの組み合わせがより大きな数になるかを確認します。
          例えば、偶数Eと奇数Oがそれぞれのキューの先頭にある場合、
          「EO」と「OE」のどちらが大きいかを比較します。
ステップ3 : より大きな組み合わせとなる要素を、最終的な並びに追加します。
ステップ4 : 最終的な並びを出力します。

C++での実装例

それでは、このアルゴリズムに基づいたプログラムを作成してみましょう。

#include <bits/stdc++.h>
using namespace std;
string merge(vector<string> arr1, vector<string> arr2) {
    int n1 = arr1.size();
    int n2 = arr2.size();
    int i = 0, j = 0;
    string big = "";
    while (i < n1 && j < n2) {
        if ((arr1[i]+arr2[j]).compare((arr2[j]+arr1[i])) > 0)
            big += arr1[i++];
        else
            big += arr2[j++];
    }
    while (i < n1)
        big += arr1[i++];
    while (j < n2)
        big += arr2[j++] ;
    return big;
}
string largestNumber(vector<string> arr, int n) {
    vector<string> even, odd;
    for (int i=0; i<n; i++) {
        int lastDigit = arr[i].at(arr[i].size() - 1) - '0';
        if (lastDigit % 2 == 0)
            even.push_back(arr[i]);
        else
            odd.push_back(arr[i]);
    }
    string biggest = merge(even, odd);
    return biggest;
}
int main() {
    vector<string> arr;
    arr.push_back("17");
    arr.push_back("80");
    arr.push_back("99");
    arr.push_back("27");
    arr.push_back("14");
    arr.push_back("22");
    int n = arr.size();
    cout<<"Biggest possible number from the array is = "<<largestNumber(arr, n);
    return 0;
}

出力結果

Biggest possible number from the array is = 801799271422

コードの解説

このプログラムの動作のポイントは以下の3点です。

• 偶数・奇数の判定(largestNumber関数): 各数値を文字列として扱い、末尾の一の位の数字を取り出して偶奇を判定します。末尾の桁さえ分かれば偶奇は確定するため、数値全体を変換する必要がなく効率的です。
• マージ処理(merge関数): マージソートの要領で、偶数列と奇数列の先頭要素を比較します。比較の際は、2つの数値を連結した文字列 (arr1[i]+arr2[j]) と (arr2[j]+arr1[i]) を辞書順で比較することで、「どちらの順で並べた方が大きくなるか」を正しく判断できます。
• 残りの要素の処理: 片方の列が空になった後は、もう片方の列の残りをそのまま連結します。これは、残りの要素同士の相対順序が保たれていれば、結果に影響しないためです。

このように、文字列比較によるマージ手法を用いることで、偶数・奇数の順序制約を満たしながら最大の数を効率的に求めることができます。