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

# 문제 설명

장르 별로 가장 많이 재생된 노래를 2개씩 모아 베스트 앨범을 출시하려고 한다. 노래는 고유번호로 구분하며, 수록 기준은 다음과 같다.

1. 장르 별로 속한 노래들의 재생 수가 많은 순으로 먼저 수록한다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록한다.
3. 재생 횟수가 같다면, 고유 번호가 낮은 노래를 먼저 수록한다.

단, 장르에 속한 곡이 하나라면 한 곡만 선택하고, 

모든 장르는 재생된 횟수가 다르다.

 

# 입출력 예시

입력	출력
genres = ["classic", "pop", "classic", "classic", "pop"] plays = [500, 600, 150, 800, 2500]	[4, 1, 3, 0]

 

# 코드 풀이

from collections import defaultdict

def solution(genres, plays):
    answer = []
    gcnt = defaultdict(int) # 장르별 재생수 합
    gbyg = defaultdict(list) # 장르별 2개씩 {g:[(p,i),]}
    for i, g, p in zip(range(len(plays)), genres, plays):
        gcnt[g] += p 
        gbyg[g].append((p, i))  # 재생수, 고유번호
    gcnt = sorted(gcnt.items(), reverse=True, key=lambda x: x[1]) # 내림차순
    
    for g, _ in gcnt:
        # 재생수 내림차순, 고유번호 오름차순
        a, *rest = sorted(gbyg[g], reverse=True, key=lambda x: (x[0],-x[1]))
        answer.append(a[1])
        if rest:
            answer.append(rest[0][1])
    return answer

 

# 핵심 포인트

• 키 값에 따라 다르게 정렬해야 한다. 문제에서 재생 수는 많은 순서부터, 고유 번호는 낮은 순서부터 정렬해야 한다. 따라서 key매개변수로 역순은 -를 곱해준다.
• 인덱스가 고유번호에 해당하여, 다른 자료구조를 만들어서 정렬된 데이터를 저장한다.