【JavaScript】トランプのカードを連続する数字のグループに再配置できるか判定する方法

本記事では、JavaScriptを用いてトランプのカードを「指定サイズの連続した数字のグループ」に再配置できるかどうかを判定するアルゴリズムを解説します。配列のソートとハッシュマップ（オブジェクト）を組み合わせたシンプルかつ効率的なアプローチを学びましょう。

問題の概要

次のようなJavaScript関数を実装することが求められます。

• 第1引数：数値の配列 arr
• 第2引数：グループのサイズを表す数値 num

配列内の各数値は [1, 13] の範囲（両端を含む）に収まっており、それぞれトランプのカードに対応しています。

この関数の目的は、すべてのカードを「サイズが num であり、かつ num 枚の連続したカードで構成される」グループに分割できるかどうかを判定することです。分割が可能であれば true を、不可能であれば false を返します。

入出力の例

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

入力

const arr = [1, 4, 3, 2];
const num = 2;

出力

true

出力の解説
このカードたちは、[1, 2] と [3, 4] の2つのグループに再配置できます。どちらのグループもサイズが2で、連続した数字で構成されているため、結果は true となります。

解決のアプローチ

この問題は、以下の手順で効率的に解くことができます。

1. 配列を昇順にソートする — 小さい数字から順に処理することで、連続性のチェックが容易になります。
2. 各カードの出現回数を記録する — オブジェクト（ハッシュマップ）を使い、同じ数字のカードが何枚あるかをカウントします。
3. 先頭のカードから順にグループ化を試みる — まだ使用されていないカードを見つけたら、そこから始まる num 枚の連続したカードがすべて存在するかを確認します。存在しなければ即座に false を返せます。
4. すべてのカードを処理できれば成功 — 全カードがグループ化できれば true を返します。

コード例

以下が実際の実装コードです。

const arr = [1, 4, 3, 2];
const num = 2;

const canRearrange = (arr = [], num = 1) => {
    // 指定した数字 n から始まる num 枚の連続カードを消費できるか確認するヘルパー関数
    const find = (map, n, num) => {
        let j = 0;
        while (j < num) {
            if (!map[n + j]) return false;
            else map[n + j] -= 1;
            j++;
        }
        return true;
    };

    let map = {};

    // 昇順にソート
    arr.sort(function(a, b) { return a - b });

    // 各カードの出現回数をカウント
    for (let n of arr) {
        map[n] = map[n] ? map[n] + 1 : 1;
    }

    // 各カードについて、未使用なら連続グループの形成を試みる
    for (let n of arr) {
        if (map[n] === 0 || find(map, n, num)) continue;
        else return false;
    }

    return true;
};

console.log(canRearrange(arr, num));

コードのポイント

• find 関数は、ある数字 n から始まる num 枚の連続したカードがすべて残っているかを確認し、存在すればマップから消費（カウントを減算）します。
• メインループでは、すでにカウントが0のカード（= 他のグループの一部として使用済み）はスキップし、残っているカードのみ新たなグループの起点として扱います。
• 途中で連続カードが揃わないケースが見つかった時点で即座に false を返すため、無駄な計算を省けます。

出力結果

true

このように、配列 [1, 4, 3, 2] はサイズ2の連続グループ [1, 2] と [3, 4] に完全に分割できるため、関数は true を返します。

まとめ

このアルゴリズムの計算量は、ソートに O(n log n)、グループ化の処理に O(n × num) かかります。ソートによって小さい方から貪欲に（greedyに）グループを形成していくことで、正しく判定できるのがポイントです。「手札をストレート（連続した数字）ごとに整理できるか」というトランプのゲームでも応用できる考え方なので、ぜひ理解を深めておきましょう。