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를 생성합니다.
모든 인덱스를 순회하면서 d[shows[i]]에 durations[i]를 더합니다. 이렇게 하면 동일한 프로그램의 시청 시간이 자동으로 합산됩니다.
딕셔너리의 값들을 새로운 리스트 l에 담습니다.
리스트 l을 내림차순으로 정렬하여 가장 많이 시청된 프로그램 순서대로 배치합니다.
인덱스 변수 i와 결과 변수 answer를 0으로 초기화합니다.
i < k인 동안 상위 k개 값을 더하고 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

출력

복잡도 분석

이 풀이의 시간 복잡도는 O(n)으로 딕셔너리에 시청 시간을 누적하는 과정이 지배하며, 정렬에는 O(m log m)이 소요됩니다(여기서 m은 고유한 프로그램 수). 전체적으로 입력 크기에 대해 선형에 가까운 효율적인 알고리즘입니다.