Pythonで解く！靴屋の在庫販売から総売上を計算するプログラム

問題の概要

ある靴屋には、サイズの異なる靴が n 足あり、それぞれのサイズは配列 size に格納されています。さらに、m 人の顧客の需要を表すペアのリスト demand が与えられ、demand[i] は (靴のサイズ, 支払額) という形式になっています。つまり、i 番目の顧客は shoe_size サイズの靴を希望しており、指定された金額を支払うことができます。このとき、店主が靴を売って得られる合計金額を求めるのがこの問題です。

入力例と出力の確認

たとえば、次のような入力が与えられたとします。

shoes = [2,3,4,5,6,8,7,6,5,18]
demand = [(6,55), (6,45), (6,55), (4,40), (18,60), (10,50)]

この場合の出力は 200 になります。その理由を順番に見てみましょう。

• 1人目の顧客は、サイズ6の靴を55で購入
• 2人目の顧客は、サイズ6の靴を45で購入
• 3人目の顧客は、在庫にサイズ6の靴が残っていないため購入できない
• 4人目の顧客は、サイズ4の靴を40で購入
• 5人目の顧客は、サイズ18の靴を60で購入
• 6人目の顧客は、サイズ10の靴が存在しないため購入できない

したがって、合計売上は 55 + 45 + 40 + 60 = 200 となります。

解法のアプローチ

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

1. n を demand の要素数として設定する
2. sizes を、サイズごとの靴の在庫数を記録するマップ（Counter）として初期化する
3. 売上を表す earn を 0 で初期化する
4. i を 0 から n-1 まで繰り返し処理する
   • (sz, price) に demand[i] を代入する
   • サイズ sz の靴が sizes に存在する場合、sizes[sz] を 1 減らし、earn に price を加算する
5. 最後に earn を返す

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

from collections import Counter
def solve(shoes, demand):
   n = len(demand)
   sizes = Counter(shoes)
   earn = 0
   for i in range(n):
      sz, price = demand[i]
      if sizes[sz]:
         sizes[sz] -= 1
         earn += price
   return earn

shoes = [2,3,4,5,6,8,7,6,5,18]
demand = [(6,55), (6,45), (6,55), (4,40), (18,60), (10,50)]
print(solve(shoes, demand))

入力

[2,3,4,5,6,8,7,6,5,18], [(6,55), (6,45), (6,55), (4,40), (18,60), (10,50)]

出力

200

コードのポイント

この実装では、Python標準ライブラリの collections.Counter を活用しています。Counter はリスト内の各要素の出現回数を自動的に集計してくれる便利なクラスで、これによりサイズごとの在庫数を簡単に管理できます。

また、Counter の特徴として、存在しないキーにアクセスした場合でもエラーにならず 0 が返されるため、「在庫があるかどうか」の判定も if 文だけでシンプルに記述できます。

計算量については、在庫のカウントに O(n)、顧客のループ処理に O(m) かかるため、全体の計算量は O(n + m) となり、非常に効率的です。在庫管理と売上計算を組み合わせた実践的なアルゴリズム問題として、ハッシュマップの使い方を学ぶのに最適な例といえるでしょう。