Pythonでn個の商品を販売した後に残る異なるIDの最小数を求めるプログラム

問題の概要

数値のリスト items と整数値 n が与えられます。営業担当者は、さまざまなIDを持つ商品をカバンに入れて所持しており、カバンの中から最大で n 個の商品を販売(削除)することができます。このとき、n 個の商品を販売し終えた後にカバンへ残る「異なるIDの種類数」の最小値を求めるのが課題です。

入力例と出力例

たとえば、items = [2, 2, 6, 6]、n = 2 の場合を考えてみましょう。このとき出力は 1 になります。同じIDを持つ商品(ID 2 または ID 6)を2つまとめて販売すれば、残る商品のIDが1種類だけで済むためです。

解決のためのアプローチ

この問題を解くには、以下の手順に従います。

• c: items 内の各要素(ID)ごとの出現頻度を記録する
• ans: c のサイズ、つまり異なるIDの総数を初期値とする
• freq: c 内のすべての頻度を昇順に並べ替えたリストを作成する
• i: 0 で初期化する
• i が freq のサイズ未満である間、以下を繰り返す:
  • freq[i] が n 以下の場合:n から freq[i] を引き(n -= freq[i])、ans を 1 減らす(ans -= 1)。これは「そのIDの商品をすべて売り切れる」ことを意味する
  • そうでない場合:これ以上IDを減らせないため、この時点での ans を返して終了する
  • i を 1 増やす
• ループを抜けたら 0 を返す

このアルゴリズムのポイントは、「出現回数が少ないIDから優先的に売り切る」という貪欲法(greedy)の発想です。在庫の少ないIDから排除していくことで、限られた販売回数 n でできるだけ多くのID種類を減らすことができます。

Pythonによる実装例

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

from collections import Counter

class Solution:
    def solve(self, items, n):
        c = Counter(items)
        ans = len(c)
        freq = sorted(c.values())
        i = 0
        while i < len(freq):
            if freq[i] <= n:
                n -= freq[i]
                ans -= 1
            else:
                return ans
            i += 1
        return 0

ob = Solution()
items = [2, 2, 6, 6]
n = 2
print(ob.solve(items, n))

入力

[2, 2, 6, 6], 2

出力

1

計算量の分析

まず Counter による頻度集計に O(len(items))、頻度リストのソートに O(m log m)(m は異なるIDの数)、最後の走査に O(m) かかります。したがって全体の時間計算量は O(len(items) + m log m)、空間計算量は O(m) となり、非常に効率的なアプローチです。