Pythonで注文リストの集配操作が有効かどうかを判定するプログラム

文字列のリスト orders があるとします。各要素は「P」または「D」で始まり、その後に注文ID番号が続きます。「P」は受取（ピックアップ）、「D」は配達を意味します。たとえば「P6」は「注文6を受け取る」ことを表します。

このリストが以下のルールに従って有効かどうかを判定する必要があります。

• 受取前に配達することはできない
• すべての受取には対応する配達が必要である
• すでに受取・配達済みの注文を再度受取または配達することはできない

たとえば、入力が orders = ["P1", "D1", "P2", "P3", "D3", "D2"] の場合、出力は True になります。これは、最初の注文が受取後に配達され、2番目と3番目の注文も一度受取られた後、最終的にすべて配達されているためです。

解決のアプローチ

この問題を解くために、次の手順に従います。

• 辞書（マップ）a を新しく作成する
• orders に重複したエントリが存在する場合は False を返す
• orders の各要素 i について処理を行う
  • i が「P」で始まる場合：受取注文番号をキーとして a[i[1:]] = 1 を設定する
  • i が「D」で始まる場合：
    • その注文番号が a に存在しなければ False を返す（未受取のまま配達しようとしているため）
    • 存在する場合は a[i[1:]] -= 1 として値を減らす（配達完了を記録）
• 最後に、a のすべての値の合計が 0 であれば True、そうでなければ False を返す

実装例

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

def solve(orders):
   a = {}
   if len(set(orders)) != len(orders):
      return False
   for i in orders:
      if i[0] == "P":
         a[i[1:]] = 1
      elif i[0] == "D":
         if i[1:] not in a:
            return False
         else:
            a[i[1:]] -= 1
   return sum(a.values()) == 0

orders = ["P1", "D1", "P2", "P3", "D3", "D2"]
print(solve(orders))

入力

["P1", "D1", "P2", "P3", "D3", "D2"]

出力

True

ポイントのまとめ

このアルゴリズムの計算量は O(n) で、リストを一度走査するだけで判定できます。重複チェックには set() を利用し、受取と配達の対応関係は辞書で管理しています。値が 1 のまま残っている注文は「受取されたが未配達」、負の値や存在しないキーへのアクセスは「不正な配達操作」を意味するため、これらを検出することでリスト全体の妥当性を正確に判断できます。