프로그래머스 Level 3 | 베스트앨범 | Python

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42579

---

문제 파악

장르 별로 노래를 두 개씩 모아서 베스트 앨범을 만들려고 한다.

노래 두개를 뽑는 규칙은 다음과 같다.
1. 속한 노래가 많이 재생된 장르를 먼저 수록한다.
2. 장르 내에서 많이 재생된 노래 순서대로 수록한다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다.

---

genres 배열을 ["classic", "pop", "classic", "classic", "pop"],
plays 배열을 [500, 600, 150, 800, 2500]

입력 받았을 때,
[4, 1, 3, 0]을 리턴해야 하는데 어떻게 된것이냐면

우선 장르별로 plays 수를 합산한다.
classic : 1,450
pop : 3,100

pop 장르가 더 많이 재생되었으므로 규칙 1의 의해 pop장르를 먼저 수록한다.

• pop
  pop장르에서 가장 많이 재생된 노래의 인덱스를 result 배열에 넣는다.
  2500회 재생된 인덱스 '4'

노래 두개씩 수록이니 그 다음으로 가장 많이 재생된 노래의 인덱스를 result 배열에 넣는다.
600회 재생된 인덱스 '1'

이제 pop 장르는 두개 다 수록 되었으니 다음 많이 재생된 classic 장르로 넘어간다.

• classic
  마찬가지로 진행하면
  800회 재생된 인덱스 '3'
  500회 재생된 인덱스 '0' 이 result배열에 차례로 들어가고

답은 [4,1,3,0] 을 return 해주면 된다.

---

어떻게 풀 수 있을까?

1. 장르별 총 재생 횟수를 비교하여 장르명을 정렬한다.
2. 장르별로 (인덱스,플레이횟수) 이렇게 나눈다.
3. 정렬된 장르명 순으로 ,장르별 두번 반복하는데, 가장 많이 플레이 한 노래 인덱스를 answer에 push한다.
4. answer를 return 한다.

해답 및 풀이

from collections import defaultdict


def solution(genres, plays):
    N = len(plays) # 노래 갯수

    # 1. 장르별 총 재생 횟수를 비교하여 장르명을 정렬한다.
    I_plays = list(enumerate(plays)) # 인덱스도 plays에 저장함 [(0,500),(1,600)...(4,2500)]

    genresAndPlay = defaultdict(list)
    for i in range(N):
        genresAndPlay[genres[i]].append(I_plays[i])
    # {'classic': [(0, 500), (2, 150), (3, 800)], 'pop': [(1, 600), (4, 2500)]}) 가 됨.

    # 장르별 총 합산 구하기
    total_by_genre = {}
    for g in genresAndPlay:
        total = 0
        for pair in genresAndPlay[g]:
            total += pair[1]
        total_by_genre[g] = total
    # total_by_genre : {'classic': 1,450, 'pop': 3,100 }

    # 장르 토탈 큰 순서대로 정렬
    genre_list = list(total_by_genre.keys()) # ['classic','pop']
    genre_list.sort(key=lambda x: total_by_genre[x], reverse=True) # 내림차순


    # 장르 내 정렬 + 상위 2곡 ansewr에 인덱스 저장
    answer = []

    for g in genre_list:
        songs = genresAndPlay[g]    
        # 곡 정렬 기준: (재생수 내림차순 -x[1], 동률일 때 x[0]-> 인덱스 오름차순)
        songs.sort(key=lambda x: (-x[1], x[0]))
        # songs = [(0, 500), (2, 150), (3, 800)] 이
        # songs = [(3, 800), (0, 500), (2, 150)] 이 됨


        cnt = 0
        for idx, _ in songs:
            answer.append(idx)
            cnt +=1 
            if cnt ==2 :
                break
    return answer

딕셔너리 안에 키(문자열) : 밸류(튜플) 형식으로 값을 집어넣는 로직과,
sort 함수에 lambda 식을 활용하여 내가 원하는 대로 정렬하는 로직에 대해 배울 수 있었다.