Pythonで顧客の列に順番どおりチケットを販売できるか判定する方法（紙幣のお釣り問題）

問題の概要

キュー（列）に並んでいる顧客がそれぞれ持っているルピー紙幣を表す配列 notes があると仮定しましょう。彼らは全員、50ルピーのチケットを1枚ずつ購入しようとしています。使用可能な紙幣は [50, 100, 200] の3種類です。

売り手は最初、手元にお金を一切持っていません（所持金0ルピー）。この状態で、並んでいる順番どおりにすべての人へチケットを販売できるかどうかを判定する必要があります。途中でお釣りを用意できなくなった場合、その時点で販売は失敗となります。

動作例

たとえば、入力が notes = [50, 50, 100, 100] の場合、答えは True になります。

最初の2人の顧客はちょうど50ルピーを支払うため、お釣りは不要です。この時点で手元には50ルピー紙幣が2枚あります。続く2人が100ルピー紙幣で支払う際には、それぞれ50ルピー紙幣をお釣りとして渡せるため、全員に順番どおりチケットを販売することができます。

解法の考え方

この問題は貪欲法（グリーディ法）で解けます。各紙幣の所持枚数を記録しながら、支払われた紙幣ごとにお釣りを返せるかを確認していきます。手順は以下のとおりです。

• freq: 各紙幣の所持枚数を管理する空のマップ（辞書）を用意します。
• i: 先頭から順に処理する位置を表すインデックスです。
• i が notes の長さ未満である限り、以下を繰り返します。
  • notes[i] が 50 の場合：お釣りは不要なので、freq[50] を1増やします。
  • notes[i] が 100 の場合：freq[100] を1増やします。freq[50] が0であればループを抜けて失敗とし、そうでなければ freq[50] を1減らしてお釣りを渡します。
  • notes[i] が 200 の場合：
    • freq[100] > 0 かつ freq[50] > 0 なら、100ルピー紙幣1枚と50ルピー紙幣1枚でお釣り150ルピーを作ります。
    • そうでなく freq[50] >= 3 なら、50ルピー紙幣3枚でお釣り150ルピーを作ります。
    • いずれも不可能な場合はループを抜けて失敗とします。
  • 処理が終わったら i を1増やします。
• 最後に i が notes の長さと一致していれば全員への販売に成功したので True を返し、途中で抜けた場合は False を返します。

なお、200ルピーを受け取った際に「100ルピー＋50ルピー」のお釣りを優先するのは、50ルピー紙幣が後続の100ルピー支払いのお釣りにも必要となる貴重な紙幣だからです。この優先順位の付け方が貪欲法の重要なポイントになります。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

from collections import defaultdict

def solve(notes):
    freq = defaultdict(int)
    i = 0
    while i < len(notes):
        if notes[i] == 50:
            freq[50] += 1
        elif notes[i] == 100:
            freq[100] += 1
            if freq[50] == 0:
                break
            freq[50] -= 1
        else:
            if freq[100] > 0 and freq[50] > 0:
                freq[100] -= 1
                freq[50] -= 1
            elif freq[50] >= 3:
                freq[50] -= 3
            else:
                break
        i += 1
    if i == len(notes):
        return True
    return False

notes = [50, 50, 100, 100]
print(solve(notes))

入力

[50, 50, 100, 100]

出力

True

まとめ

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n) です。また、管理対象の紙幣の種類が固定されているため、空間計算量は O(1) で済みます。お釣りの組み合わせの優先順位（100ルピー＋50ルピーを優先）を正しく選ぶことが、この問題を効率よく解く鍵となります。