貪欲で札を連続する数の組に分ける

数の書かれた札の束を、決まった枚数の連続する数の組に全部分けられるかを返す。残っている最も小さい札は必ず組の先頭になるので、小さい順に組を作っていくだけで判定できます。

海外で定番の問題リスト 4 本には入っていません

問題

カードゲームで、数の書かれた札の並び cards と、組の枚数 size が渡されます。札を全部使い、どの組も size 枚の連続する数 (たとえば 4、5、6) でできるように分けられるなら true、分けられないなら false を返す関数を書いてください。

同じ数の札が何枚あることもあります。1 つの組の中に同じ数は入りません
cards の枚数が size で割り切れなければ、分けられないので false です
size が 1 なら、どの札も 1 枚で組になるので true です
cards の長さは 1 以上 10000 以下、値はどれも 0 以上 1000000000 以下、size は 1 以上 cards の長さ以下です

入力と出力の例

例 1

[3, 4, 5]、[4, 5, 6]、[10, 11, 12] の 3 組に分けられます。

cards = [5, 3, 4, 10, 11, 12, 4, 6, 5] size = 3

true

例 2

2 を含む組は [2, 3] しかなく、残りの 4, 4, 5, 6 では 4 が 2 枚とも 5 を要るのに、5 は 1 枚しかありません。

cards = [2, 3, 4, 4, 5, 6] size = 2

false

例 3

4 枚は 3 で割り切れないので、数を見るまでもなく分けられません。

cards = [8, 9, 10, 11] size = 3

false

面接での聞かれ方

面接では、トランプやカードゲームの話として出されることが多いです。

「手札を、同じ枚数の連番の組に分けられますか」
「同じ数の札は何枚ありますか」と聞くと、「何枚でもあります」と返ってくるのがふつうです
書き終えたあとに「値の幅が小さいと分かっているなら速くできますか」と、続きを聞かれることもあります

同じ数の札が複数あるか、組の中で同じ数を使えるかを、書く前に確かめておきます。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

素直に考えると、組の作り方を全部試すことになります。どの札をどの組に入れるかの組み合わせはとても多く、札が増えると終わりません。

段 2

いま残っている札のうち最も小さい数 x を考えます。x より小さい札は残っていないので、x を含む組は x から始まる x, x + 1, ..., x + size - 1 しかありません。迷う所が無いので、この組を作ってよいと分かります。

段 3

数ごとの枚数を数え、数を小さい順に見ます。数 x がまだ c 枚残っていれば、x から始まる組を c 組まとめて作ります。x + 1 から x + size - 1 までの数をそれぞれ c 枚ずつ減らし、どれかが足りなければ false です。最後まで足りれば true です。

解答

Python

from collections import Counter


def can_split_straights(cards, size):
    if len(cards) % size != 0:
        return False
    count = Counter(cards)
    for x in sorted(count):
        c = count[x]
        if c == 0:
            continue
        for y in range(x, x + size):
            if count[y] < c:
                return False
            count[y] -= c
    return True

JavaScript

function canSplitStraights(
  cards, size
) {
  if (cards.length % size !== 0) {
    return false;
  }
  const count = new Map();
  for (const x of cards) {
    count.set(
      x, (count.get(x) ?? 0) + 1,
    );
  }
  const keys = [...count.keys()];
  keys.sort((p, q) => p - q);
  for (const x of keys) {
    const c = count.get(x);
    if (c === 0) {
      continue;
    }
    for (
      let y = x;
      y < x + size;
      y++
    ) {
      const have = count.get(y) ?? 0;
      if (have < c) {
        return false;
      }
      count.set(y, have - c);
    }
  }
  return true;
}

Go

import "slices"

func canSplitStraights(
	cards []int, size int,
) bool {
	if len(cards)%size != 0 {
		return false
	}
	count := map[int]int{}
	for _, x := range cards {
		count[x]++
	}
	keys := make([]int, 0,
		len(count))
	for x := range count {
		keys = append(keys, x)
	}
	slices.Sort(keys)
	for _, x := range keys {
		c := count[x]
		if c == 0 {
			continue
		}
		for y := x; y < x+size; y++ {
			if count[y] < c {
				return false
			}
			count[y] -= c
		}
	}
	return true
}

Go の map を range で回す順は毎回変わるので、数を取り出してから並べ替えています。Python の Counter は、無い数を引くと 0 を返すので、count[y] をそのまま比べられます。

計算量

時間は O(n log n + n × size) です。異なる数を並べ替えるのに O(n log n)、組を作るときに数ごとに size 個の数を減らします
使う記憶は O(n) です。数ごとの枚数と、並べた数の一覧を持ちます
組をまとめて c 組ずつ作るので、同じ数の札が多くても、減らす回数は異なる数の個数 × size で済みます

よくある間違い

並べ替えずに数を見る。数え上げた順のまま見ると、例 1 では最初に出てくる 5 から [5, 6, 7] を作ろうとし、7 が無いので、分けられるのに false を返します。最も小さい数から見るから、迷わずに組が決まります
組を 1 組ずつ作るたびに並べ直す。札を 1 枚ずつ取り出して並べ直すと、手間が O(n² log n) まで増えます。枚数を数えておけば、同じ数の組をまとめて作れます
割り切れるかを確かめない。例 3 は数が連続していても、4 枚は 3 で割り切れないので分けられません。先に確かめると、無駄な数え上げをせずに済みます
数の値で引く並びを作る。値の幅で長さを決めた並びに枚数を入れると、値が 1000000000 まであるので記憶が足りません。枚数は辞書で持ち、出てくる数だけを並べ替えます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def can_split_straights(cards: list[int], size: int) -> bool:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(can_split_straights([5, 3, 4, 10, 11, 12, 4, 6, 5], 3))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します