프로그래머스 알고리즘: 베스트앨범 (lv3)

https://school.programmers.co.kr/learn/courses/30/lessons/42579?language=python3

from heapq import heapify, heappop, heappush
from collections import Counter

def solution(genres, plays):
    dic = {}
    cnt_dic = Counter() # 장르의 총 재생수 계산용
    # O(NlogN)
    for idx, (gener, play) in enumerate(zip(genres, plays)):
        if gener in dic:
            heappush(dic[gener], (-play, idx)) # O(logN)
            cnt_dic[gener] += play
        else:
            # 내림차순 정렬을 위해 음수로 변환
            dic[gener] = [(-play, idx)]
            cnt_dic[gener] = play
    
    answer = []
    # O(NlogN)
    for gener, _ in cnt_dic.most_common():
        try:
            __, idx = heappop(dic[gener])
            answer.append(idx)
            __, idx = heappop(dic[gener])
            answer.append(idx)
        except:
            # dic[gener] 의 value가 두 개 미만인 경우 발생
            # 있는 것만 출력하면 되므로 없으면 pass 함
            pass
    
    return answer

• 시간복잡도 O(NlogN)으로 추정

• value 값이 많은 두 key를 뽑기 위해 Counter 클래스 사용
  이 문제로 처음 알게 되었는데 유용할 듯 싶다

• 장르 내 노래 정렬을 위해 value가 heap인 딕셔너리 사용

• if-else 문보단 try-except문 을 사용하라고 배웠는데 잘 쓰고 있는 것 같다

  • 사소하지만 필요없는 변수는 _ 으로 처리하는 것도..!