Pythonで解くレモネード釣り銭問題：貪欲法による実装と解説

レモネードスタンドの釣り銭問題とは？

レモネードスタンドを想像してみてください。レモネード1杯の価格は5ドルで、客は列に並んで順番に1杯ずつ購入していきます。

各客が支払いに使えるのは、5ドル札・10ドル札・20ドル札のいずれかです。店側はすべての客に対して正確な釣り銭を用意し、実質的に客が5ドルを支払う形にしなければなりません。しかも、開店時点では手元に釣り銭が1枚もない状態から始まります。

この記事では、「すべての客に正しく釣り銭を渡すことができるか？」を判定するアルゴリズムを、Pythonで実装しながら解説します。

入力例と出力例

たとえば、支払いの順序が [5, 5, 5, 10, 20] だった場合を考えてみましょう。このときの出力は True になります。

• 1〜3人目： 5ドル札で支払うため釣り銭は不要。手元に5ドル札が3枚たまります。
• 4人目： 10ドル札で支払うため、おつりとして5ドル札を1枚渡します（残り2枚）。
• 5人目： 20ドル札で支払うため、10ドル札1枚と5ドル札1枚、計15ドルをおつりとして渡します。

このように全員に正確な釣り銭を渡せたため、結果は True となります。

解法のアプローチ：貪欲法

この問題は貪欲法（グリーディ法）で効率よく解けます。鍵となるのは、20ドル札を受け取ったときのおつりの渡し方です。

15ドルのおつりは「10ドル札＋5ドル札」または「5ドル札×3枚」の2通りで作れます。ここで10ドル札と5ドル札の組み合わせを優先するのがポイントです。5ドル札はあらゆるおつりに使える万能な紙幣なので、できるだけ手元に残しておくのが得策だからです。

アルゴリズムの手順

1. 手持ちの紙幣を管理する変数 n5（5ドル札の枚数）、n10（10ドル札の枚数）、n20（20ドル札の枚数）を0で初期化します。
2. 支払いリスト bills の各要素 i について、以下の処理を繰り返します。
   • i が5なら n5 を+1、10なら n10 を+1、それ以外（20）なら n20 を+1します。
   • 5ドル札が1枚もない状態（n5 == 0）であれば、10ドル以上の支払いに対応できないため False を返します。
   • i が20の場合：
     • n10 > 0 かつ n5 > 0 なら、10ドル札1枚と5ドル札1枚でおつりを作ります（両方を-1）。
     • n10 == 0 かつ n5 < 3 なら、おつりを作れないため False を返します。
     • n10 == 0 かつ n5 >= 3 なら、5ドル札3枚でおつりを作ります（n5 を-3）。
   • i が10の場合：
     • n5 > 0 なら、5ドル札1枚をおつりとして渡します（n5 を-1）。
     • n5 == 0 なら、おつりを作れないため False を返します。
3. すべての客に対応できたら True を返します。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def lemonadeChange(self, bills):
        n5 = 0
        n10 = 0
        n20 = 0
        for i in bills:
            if i == 5:
                n5 += 1
            elif i == 10:
                n10 += 1
            else:
                n20 += 1
            if len(bills) > 0 and n5 == 0:
                return(False)
            if i == 20 and n10 > 0 and n5 > 0:
                n10 -= 1
                n5 -= 1
            elif i == 20 and n10 == 0 and n5 < 3:
                return(False)
            elif i == 20 and n10 == 0 and n5 >= 3:
                n5 = n5 - 3
            if i == 10 and n5 > 0:
                n5 -= 1
            elif i == 10 and n5 == 0:
                return (False)
        return(True)

ob = Solution()
print(ob.lemonadeChange([5,5,5,10,20]))

入力

[5,5,5,10,20]

出力

True

まとめ

レモネード釣り銭問題は、紙幣の種類が5種類と限られているため、貪欲法によってO(n)の計算量で解けるシンプルなシミュレーション問題です。重要なのは「20ドル札のおつりには、可能な限り10ドル札を使う」という優先順位の付け方です。5ドル札はどんなおつりにも使えるため、これを温存する判断が全体の成否を左右します。この発想は、両替システムや自動販売機の釣り銭管理など、実務の金銭処理ロジックにも応用できる考え方です。