JavaScriptで2つの配列から作れる最大の数を求める方法

問題

1桁の数字を要素とする2つの配列 arr1 と arr2 を第1・第2引数として受け取り、さらに数値 num(num <= arr1.length + arr2.length)を第3引数として受け取るJavaScript関数を作成します。

この関数が返すのは、長さ num の1桁の数字からなる新しい配列です。この配列自体が1つの数値を表しており、その値は両方の配列の要素を組み合わせて作成できる最大の数でなければなりません。

ただし、重要な条件がひとつあります。それは、同じ配列内の要素の相対的な順序は維持しなければならないという点です。

例えば、関数への入力が次の場合を考えてみましょう。

const arr1 = [1, 3, 4, 5, 6];
const arr2 = [9, 1, 2, 5, 8, 3];
const num = 4;

この場合、期待される出力は次のとおりです。

const output = [9, 8, 6, 3];

つまり、「9863」という最大の数を、各配列の元の順序を崩すことなく作り出しています。

サンプルコード

この問題を解くコードは次のようになります。

const arr1 = [1, 3, 4, 5, 6];
const arr2 = [9, 1, 2, 5, 8, 3];
const num = 4;
const maxArray = (arr1 = [], arr2 = [], num) => {
   const map = new Map();
   const match = (a, b, num) => {
      if (map.has(a + ',' + b + ',' + num)) {
         return map.get(a + ',' + b + ',' + num);
      }
      let output = [];
      while(num > 0) {
         let maxa = -Infinity;
         let maxai = 0;
         let maxb = -Infinity;
         let maxbi = 0;
         for(let i = a; i < arr1.length && arr1.length + arr2.length - (i + b) >= num; i++) {
            if (arr1[i] > maxa) {
               maxa = arr1[i];
               maxai = i;
            }
         }
         for(let i = b; i < arr2.length && arr1.length + arr2.length - (a + i) >= num; i++) {
            if (arr2[i] > maxb) {
               maxb = arr2[i];
               maxbi = i;
            }
         }
         if (maxa === maxb) {
            output.push(maxa);
            let ca = map.get(a+','+(maxbi+1)+','+(num-1)) || match(a, maxbi+1, num-1);
            let cb = map.get((maxai+1)+','+b+','+(num-1)) || match(maxai+1,b,num-1);
            map.set(a+','+(maxbi+1)+','+(num-1), ca);
            map.set((maxai+1)+','+b+','+(num-1), cb);
            if (ca.join('') > cb.join('')) {
               return [...output, ...ca];
            } else {
               return [...output, ...cb];
            }
         } else if (maxa > maxb) {
            output.push(maxa);
            a = maxai + 1;
         } else {
            output.push(maxb);
            b = maxbi + 1;
         }
         num--;
      }
      map.set(a + ',' + b + ',' + num, output);
      return output;
   }
   return match(0, 0, num);
};
console.log(maxArray(arr1, arr2, num));

コードの解説

このアルゴリズムでは、次のような手順で最大の数を組み立てています。

• 残りの桁数(num)を満たせる範囲に制限しながら、forループで各配列から選べる最大の数字を探します。

• arr1 側の候補の方が大きければ arr1 の数字を採用し、そうでなければ arr2 の数字を採用します。

• 両方の配列に同じ数字がある場合は、どちらを選んでも結果が変わる可能性があるため、再帰的にその後の結果を比較し、より大きな数になる方を選びます。

また、同じ状態(開始位置と残り桁数の組み合わせ)の計算結果を Map オブジェクトにキャッシュすることで、重複する再帰計算を避け、パフォーマンスを向上させています。これはメモ化(memoization)と呼ばれるテクニックです。

出力

コンソールには次のように出力されます。

[ 9, 8, 6, 3 ]