JavaScriptで配列をシャッフルし、相手配列に対する勝利数を最大化する方法

問題概要

同じ長さを持つ2つの数値配列 arr1 と arr2 を受け取り、arr1 の要素をシャッフルすることで、arr2 の対応する要素よりも大きい要素の数を最大限に増やすJavaScript関数を作成します。最終的に、シャッフル後の配列を返します。

例えば、次のような入力があった場合を考えてみましょう。

入力:

const arr1 = [3, 5, 12, 19];
const arr2 = [2, 9, 3, 12];

出力:

const output = [3, 12, 5, 19];

出力の説明:

シャッフル前の arr1 では、arr2 より大きい対応要素は3つでしたが、シャッフル後は4つすべての要素が対応する要素を上回っています。

解き方の考え方（貪欲法）

この問題は貪欲法（グリーディーアルゴリズム）を使うことで効率的に解けます。基本的な戦略は以下の通りです。

• arr1 を降順にソートしておく
• arr2 の値が大きい位置（インデックス）から順に処理する
• 各位置において、まだ使っていない arr1 の最大値が arr2 のその位置の値より大きければ、その最大値を割り当てる
• 勝てそうにない場合は、あえて最小値を割り当てて、大きな値を他の場所のために温存する

コード例

const arr1 = [3, 5, 12, 19];
const arr2 = [2, 9, 3, 12];
const maximiseArray = (arr1 = [], arr2 = []) => {
    arr1.sort((a, b) => b - a)
    const indexes = arr2.map((v, index) => index).sort((a, b) => arr2[b] - arr2[a])
    const res = []
    for(let i = 0; i < indexes.length; i++) {
        const index = indexes[i]
        res[index] = arr1[0] > arr2[index] ? arr1.shift() : arr1.pop()
    }
    return res
}
console.log(maximiseArray(arr1, arr2));

実行結果

[ 3, 12, 5, 19 ]

コードの解説

このコードの動作を順を追って見ていきましょう。

1. arr1.sort((a, b) => b - a) — arr1 を降順にソートし、常に先頭に最大値が来る状態を保ちます。
2. indexes — arr2 の各要素のインデックスを、対応する値が大きい順に並べ替えた配列です。
3. ループ内では、arr2 の値が大きいインデックスから順に処理し、残りの最大値 arr1[0] がその位置の値より大きければ shift() で先頭の値を使います。そうでなければ pop() で末尾（最小値）を犠牲にします。
4. これにより、勝てる場所には強い数字を割り当て、勝てない場所には惜しくない弱い数字を割り当てることができます。

全体の計算量はソートが支配的となり、O(n log n) で収まるため、大規模な配列でも高速に動作します。