C++でn人ごとの顧客に割引を適用するCashierクラスの実装方法

問題概要

スーパーマーケットでセールが開催されており、n人ごとに割引が適用されるというシナリオを考えてみましょう。店内には複数の商品があり、i番目の商品IDは products[i]、その商品の単価は prices[i] で表されます。

システムは来店客を順番にカウントし、n番目の客が到着したタイミングで、その客の請求額に対して割引を適用します。割引適用後はカウントがリセットされ、再び0から数え始めます。顧客はそれぞれの商品を任意の数量だけ注文します。product[i] が注文されたi番目の商品ID、amount[i] がその注文数量です。この仕組みを Cashierクラス として実装します。クラスが持つべきメソッドは以下の通りです。

• Cashier(int n, int discount, int[] products, int[] prices): 割引間隔n、割引率discount、商品IDの配列products、対応する単価の配列pricesを受け取り、オブジェクトを初期化するコンストラクタです。

• double getBill(int[] product, int[] amount): 請求金額を計算して返し、該当する場合には割引を適用します。実際の値との誤差が10^-5以内であれば正解とみなされます。

例として、Cashier(3, 50, [1,2,3,4,5,6,7], [100,200,300,400,300,200,100]) で初期化し、getBillメソッドを順番に呼び出します。

getBill([1,2],[1,2]), getBill([3,7],[10,10]), getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]), getBill([4],[10]), getBill([7,3],[10,10]), getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]), getBill([2,3,5],[5,3,2])

このとき、期待される出力は以下の通りです。3回目と6回目の呼び出し(3の倍数番目に相当する顧客)だけで半額の割引が適用されている点に注目してください。

[500.0, 4000.0, 800.0, 4000.0, 4000.0, 7350.0, 2500.0]

解法のアプローチ

この問題を解くために、まず商品IDをキー、単価を値とするマップ order を定義しておきます。そのうえで、以下の手順で処理を組み立てます。

コンストラクタの処理

• 顧客カウンタ curr を0で初期化します。
• i を0からprices配列のサイズまでループし、order[products[i]] = prices[i] として商品IDと単価の対応を登録します。
• 引数で渡された割引間隔nと割引率discountをメンバ変数に保存します。

getBillメソッドの処理

• curr を1増やします。そのうえで、curr == n ならフラグflagをtrue、そうでなければfalseに設定します。
• curr == n の場合、curr を0に戻してカウントをリセットします。
• 合計金額 ret を0で初期化します。
• i を0からproduct配列のサイズ-1までループします。
  • x := product[i](商品ID)
  • cost := order[x](単価)
  • y := amount[i](注文数量)
  • ret += cost × y で合計金額を積算します。
• flagがtrueの場合、ret = ret - (ret * discount) / 100 で割引を適用します。
• ret を返します。

C++での実装例

それでは、上記のロジックを実際のC++コードで確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Cashier {
public:
   int curr;
   map <double, double> order;
   int n;
   int discount;
   Cashier(int n, int discount, vector<int>& pro, vector<int>& p) {
      curr = 0;
      for(int i = 0; i < p.size(); i++){
         order[pro[i]] = p[i];
      }
      this->n = n;
      this->discount = discount;
   }
   double getBill(vector<int> pro, vector<int> am) {
      curr++;
      bool flag = curr == n;
      if(curr == n){
         curr = 0;
      }
      double ret = 0;
      for(int i = 0; i < pro.size(); i++){
         double x = pro[i];
         double cost = order[x];
         double y = am[i];
         ret += (cost * y);
      }
      if(flag) ret = ret - (ret * discount) / 100;
      return ret;
   }
};
main(){
   vector<int> v1 = {1,2,3,4,5,6,7}, v2 =
   {100,200,300,400,300,200,100};
   Cashier ob(3, 50, v1, v2);
   v1 = {1,2}, v2 = {1,2};
   cout << (ob.getBill(v1, v2)) << endl;
   v1 = {3,7}, v2 = {10,10};
   cout << (ob.getBill(v1, v2)) << endl;
   v1 = {1,2,3,4,5,6,7}, v2 = {1,1,1,1,1,1,1};
   cout << (ob.getBill(v1, v2)) << endl;
   v1 = {4}, v2 = {10};
   cout << (ob.getBill(v1, v2)) << endl;
   v1 = {7,3}, v2 = {10,10};
   cout << (ob.getBill(v1, v2)) << endl;
   v1 = {7,5,3,1,6,4,2}, v2 = {10,10,10,9,9,9,7};
   cout << (ob.getBill(v1, v2)) << endl;
   v1 = {2,3,5}, v2 = {5,2,3};
   cout << (ob.getBill(v1, v2)) << endl;
}

入力

main関数内で行われる一連のgetBillメソッドの呼び出しが入力となります。

出力

500
4000
800
4000
4000
7350
2500

まとめ・実装のポイント

この実装のポイントは、商品IDから単価への対応を std::map(連想配列)に事前登録しておくことで、請求計算時に単価を即座に参照できる点にあります。また、顧客カウンタ curr はnに達すると0へ戻るため、「n人ごと」という割引サイクルが永続的に繰り返されます。計算量としては、初期化に商品種類数をPとしてO(P)、1回の請求計算につき注文商品数をmとしてO(m log P)程度に収まり、実用的かつ効率的な設計です。