프로그래머스: [베스트앨범]

📌 프로그래머스: [베스트앨범]

🔗 문제 링크

---

문제 설명 📄

장르별로 가장 많이 재생된 곡을 우선적으로 선택하여 앨범을 구성한다.
장르별로 최대 2곡씩 선택하며, 재생 횟수가 같다면 고유 번호가 작은 순서대로 정렬한다.
장르의 순서는 총 재생 횟수가 높은 순서대로 정렬한다.

---

문제 접근 방식 💡

• 장르별로 곡을 묶고, 각 곡을 (재생 횟수, 고유 번호) 기준으로 정렬한다.
• 장르별 총 재생 횟수를 기준으로 내림차순 정렬하여, 가장 인기 있는 장르부터 선택한다.
• 각 장르에서 최대 2곡을 선택하며, 재생 횟수가 같다면 고유 번호가 작은 순서대로 정렬한다.
• 우선순위 큐(heapq)를 활용하여 정렬을 효율적으로 수행한다.

---

Solution 💻

from collections import defaultdict
import heapq

def solution(genres, plays):
    pattern = defaultdict(list)
    
    for i, (gen, play) in enumerate(zip(genres, plays)):
        heapq.heappush(pattern[gen], (-play, i)) 

    q = []
    for key, value in pattern.items():
        total = sum(-i[0] for i in value) 
        heapq.heappush(q, (-total, key))

    answer = []
    while q:
        key, value = heapq.heappop(q) 
        for _ in range(2):
            if pattern[value]: 
                answer.append(heapq.heappop(pattern[value])[1])

    return answer

시간 복잡도 분석 ⏲️

• 장르별로 곡을 저장하는 과정: O(N log N)
• 장르별 총 재생 횟수를 계산하는 과정: O(N)
• 힙을 이용한 정렬 및 선택: O(N log N)
• 총 시간 복잡도: O(N log N), N은 곡의 개수

공간 복잡도 분석 🗄️

• 공간 복잡도: O(N)
  • pattern 딕셔너리 및 heapq를 이용한 저장 구조 활용.