Pythonで最も視聴された上位K番組の合計視聴時間を求めるプログラム

文字列のリスト shows、整数のリスト durations、そして値 k が与えられたとします。shows[i] と durations[i] は、i 番目の人が視聴した番組名とその視聴時間を表しています。このとき、最も視聴された上位 k 件の番組について、合計視聴時間を求めるのがこの問題の目的です。

例えば、入力が次のような場合を考えてみましょう。

• shows = ["The BGT", "Jack jumper", "The BGT", "Jokers Company", "Music magic"]
• durations = [10, 8, 10, 18, 9]
• k = 2

この場合の出力は 38 になります。最も視聴された上位2つの番組は「Jokers Company」(18分)と「The BGT」(10 + 10 = 20分)であり、18 + 20 = 38 となるためです。

解決のアプローチ

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

• shows または durations が空、あるいは k が 0 の場合は 0 を返す
• 空の辞書 d(defaultdict)を用意する
• i を 0 から shows の要素数までループし、d[shows[i]] に durations[i] を加算して、番組ごとの視聴時間を集計する
• 新しいリスト l を作成し、辞書 d の各値(番組ごとの合計視聴時間)を追加する
• リスト l を降順にソートする
• i と answer を 0 に初期化し、i < k の間、answer に l[i] を加算していく
• answer を返す

実装例

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

from collections import defaultdict

def solve(shows, durations, k):
    if not shows or not durations or not k:
        return 0

    d = defaultdict(int)

    for i in range(len(shows)):
        d[shows[i]] += durations[i]

    l = []
    for i in d:
        l.append(d[i])
    l.sort(reverse=True)
    i = 0
    answer = 0
    while i < k:
        answer += l[i]
        i += 1
    return answer

shows = ["The BGT", "Jack jumper", "The BGT", "Jokers Company",
"Music magic"]
durations = [10, 8, 10, 18, 9]
k = 2
print(solve(shows, durations, k))

入力

["The BGT", "Jack jumper", "The BGT", "Jokers Company", "Music magic"], [10, 8, 10, 18, 9], 2

出力

38

計算量について

このアルゴリズムの時間計算量は O(n log n) です(n はレコードの総数)。すべての視聴記録を集計するのに O(n)、ソートに O(n log n) かかるためです。空間計算量は O(m)(m はユニークな番組数)で、辞書とリストに必要なメモリを格納します。

より簡潔な実装例(Counter を活用)

Python の標準ライブラリ Collections.Counter を使うと、同じ処理をより簡潔に書くこともできます。

from collections import Counter

def solve(shows, durations, k):
    counter = Counter()
    for show, duration in zip(shows, durations):
        counter[show] += duration
    return sum(sorted(counter.values(), reverse=True)[:k])

zip() を使うことで番組名と視聴時間をペアで処理でき、コードの可読性が向上します。また、heapq.nlargest(k, counter.values()) を使えば、全要素をソートせずに上位 k 件だけを効率的に取得することも可能です。