Pythonで特別割引セールの最終支払額を求めるプログラムの書き方

「prices」という配列があるとします。ここで prices[i] は、店で販売されている i 番目の商品の価格を表します。現在この店では特別なセールが実施されており、i 番目の商品を購入すると、「j > i を満たす最小のインデックス j であり、かつ prices[j] <= prices[i]（j 番目の商品の価格が i 番目の商品の価格以下）」という条件を満たす商品が存在する場合、その prices[j] に相当する金額の割引を受けられます。該当する商品が存在しない場合は、割引は一切適用されません。

この記事では、この特別割引を考慮したうえで、i 番目の商品に対して実際に支払う最終価格を要素とする配列を求めるプログラムを Python で実装します。

問題の具体例

入力が prices = [16, 8, 12, 4, 6] の場合、出力は [8, 4, 8, 4, 6] になります。それぞれの商品について確認してみましょう。

• 商品0（価格16）： 右側で最初に自分以下の価格になるのは prices[1] = 8 なので、8 の割引が適用され、最終価格は 16 − 8 = 8 となります。
• 商品1（価格8）： 右側で最初に自分以下の価格になるのは prices[3] = 4 なので、4 の割引が適用され、最終価格は 8 − 4 = 4 となります。
• 商品2（価格12）： 右側で最初に自分以下の価格になるのは prices[3] = 4 なので、4 の割引が適用され、最終価格は 12 − 4 = 8 となります。
• 商品3（価格4）・商品4（価格6）： 右側に自分以下の価格の商品が存在しないため、割引は適用されず、それぞれ 4 と 6 のままです。

解法のアプローチ

最も直感的な方法は、各商品について右側の商品を順番に調べ、最初に見つかった「自分以下の価格」を割引として差し引くというものです。手順は以下の通りです。

• i を 0 から prices のサイズ未満まで繰り返す
  • j を i+1 から prices のサイズ未満まで繰り返す
    • prices[i] >= prices[j] であれば
      • prices[i] = prices[i] - prices[j] とする
      • 内側のループを抜ける
    • そうでなければ、次の j へ進む
• すべての処理が完了したら prices を返す

Pythonでの実装例

以下が実際の実装コードです。

def solve(prices):
    for i in range(len(prices)):
        for j in range(i+1, len(prices)):
            if prices[i] >= prices[j]:
                prices[i] -= prices[j]
                break
    return prices

prices = [16, 8, 12, 4, 6]
print(solve(prices))

入力

[16, 8, 12, 4, 6]

出力

[8, 4, 8, 4, 6]

計算量と効率化のポイント

この実装では、外側のループと内側のループが組み合わさるため、時間計算量は O(n²) になります。商品数が少ない場合は十分実用的ですが、データ件数が多い場合は注意が必要です。

より効率化したい場合は、スタック（Stack）を活用する手法が有効です。インデックスをスタックに積みながら走査し、現在の価格がスタック top の価格以下になったタイミングで割引を適用することで、各要素の push / pop は高々1回ずつしか発生せず、時間計算量を O(n) まで削減できます。大量のデータを扱う実務の場面では、こちらのアプローチを検討するとよいでしょう。