❓프로그래머스 : 베스트 앨범
📈 문제 요약
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아서 베스트 앨범을 출시하려 할 때 다음 기준에 맞춰서 노래를 수록하면 되는 문제
- 속한 노래가 많이 재생된 장르를 먼저 수록
- 장르 내에서 많이 재생된 노래를 먼저 수록
- 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록
🤨 접근법
일단 각 장르에서 음악을 최대 두 곡씩 뽑게 되면 정렬되는 기준은 명확했기 때문에 각 정보를 파싱해서 한 번에 리스트에 담아 람다식으로 정렬하고자 하였다.
우선 속한 노래가 많이 재생된 장르를 먼저 수록한다는 조건을 위해 각 장르 별 노래의 재생 횟수를 알아야 한다. 각 장르명을 key로 하고 장르에 속한 음악의 재생 횟수를 value로 하는 dict를 활용해 저장했다.
다음 각 장르마다 노래의 재생 횟수와 고유 번호를 알아야한다. 각 장르명을 key로 하고 (음악 횟수, 고유 번호)를 원소로 가지는 힙을 value로 하는 dict를 활용해 저장했다. 이 때 각 장르에서 음악 재생 횟수가 가장 높은 최대 2개의 노래를 수록할 수 있기 때문에 힙을 활용할 때 음악 재생 횟수를 기준으로 하는 최대 힙으로 활용하였다. 힙에 push할 때 음악 재생 횟수에 -를 붙여 push한다.
이제 최종적으로 수록곡을 담는 리스트에 각 장르마다 최대 두 곡씩 담는다. 음악의 정보는 각 최대 힙에 담겨있으므로 힙에서 하나씩 pop하여 넣는다. 이때 이전에 구한 해당 음악이 속한 장르의 재생횟수를 함께 append한다. 이는 마지막에 한 번에 정렬을 하기 위함이다. pop할 때 힙이 비어있는지 검사하여 장르에 속한 곡이 하나일 때 하나의 곡만 담기도록 하였다.
마지막으로 결과 리스트를 람다식을 통해 정렬한다. [**0]번째 인덱스에 해당하는 장르 내 노래의 총 재생 횟수는 내림차순, [1]번째 인덱스에 해당하는 해당 노래의 재생 횟수는 내림차순, [2]번째 인덱스에 해당하는 해당 노래의 고유 번호는 오름차순으로 정렬**하여 문제를 해결하였다.
🔡 코드
from collections import defaultdict
from heapq import heappush, heappop
def solution(genres, plays):
music_dict = defaultdict(list)
count_dict = defaultdict(int)
result = []
for genre,play in zip(genres, plays):
count_dict[genre] += play
for idx, genre, play in zip(range(len(genres)), genres, plays):
heappush(music_dict[genre], (-play, idx)) # max heap
for key, value in music_dict.items():
for _ in range(2):
play, idx = heappop(music_dict[key])
result.append((count_dict[key], -play, idx))
if not music_dict[key]:
break
return [idx for _, _, idx in sorted(result, key = lambda x : (-x[0], -x[1], x[2]))]