[Programmers] 베스트앨범

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

해설

장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 만드는 프로그램을 완성하는 것이다. 입력 값으로 노래의 장르를 나타내는 문자열 배열 genres, 노래별 재생횟수를 나타내는 정수 배열 plays가 주어진다. 이때 노래마다 고유번호가 존재하고 그 고유 번호를 i 라고 했을 때, genres[i]는 i 노래의 장르를 나타내고 plays[i]는 i 노래의 재생횟수를 나타낸다.

문제의 노래 수록 기준은 다음과 간다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록한다. -> 이 기준에 따라서 장르별 총 재생횟수를 구하고 정렬해야 함을 알 수 있다.

2. 장르 내에서 많이 재생된 노래를 먼저 수록한다. -> 이 기준을 보고 특정 장르에 속한 노래를 재생횟수별로 정렬해야 함을 알 수 있다.

3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. -> 마지막 기준을 보았을 때 2번의 정렬을 할때 재생횟수가 같은 값이 있다면 낮은 번호순으로 정렬해야함을 알 수 있다.

이 세가지 기준을 살펴 보았을 때 장르와 장르의 총 재생횟수가 key와 value의 관계를 갖고, 장르와 (노래번호, 재생횟수)가 key value의 관계를 갖는것을 알 수 있다.

이 대로 정리해보면

"classic": [1450, [(0,500), (2,150), (3,800)] ]

"pop": [3100, [(1,600), (4,2500)] ]

여기서 장르별 총 재생횟수는 pop이 3100으로 가장 많고 그 다음은 1400회인 classic이다. 그러므로 1번 기준에 따라 pop 장르의 노래부터 베스트 앨범에 수록한다. 이때 2,3번 기준에 따라 pop 장르 내에서 노래 정보를 정렬을 하면[(4,2500), (1,600)]이다. 그러므로 4번노래와 1번 노래를 삽입하면 된다. [4,1]

다시 1번 기준에 따라서 그 다음으로 많은 재생횟수를 가진 classic 장르의 노래를 삽입한다. 그리고 classic 장르의 노래를 2,3번 기준에 의해 정렬하면 [(3,800), (0,500), (2,150)]이다. 이때 제한 사항을 보면 장르 별로 가장 많이 재생된 노래 두 개씩 삽입한다고 했다. [(3,800), (0,500)] 이다. 그러므로 [3,0]을 베스트앨범에 추가하면 된다.

위 과정을 알고리즘으로 정리하면 아래와 같다.

 

 

1. 장르별 총 재생 수를 구한다.(이때 해시를 통해 저장한다. 총 재생횟수를 구하면서 동시에 노래번호와 재생횟수를 같이 value에 리스트형태(요소의 값은 재생횟수, 노래번호)로 저장한다. {장르: [총 재생횟수, [(i노래 재생횟수,i),(j노래 재생횟수, j)]]} )

 

2. 1에서 구한 값으로 가장 많이 재생된 장르를 선정하는데, 선정 방법은 해시에 저장된 모든 value를 총 재생횟수 기준 내림차순 정렬하여 반복문으로 하나씩 불러내는 방식을 사용한다.

3. 2번에서 정렬된 데이터에서 순서 대로 반복문을 돌면서 데이터를 추출하면서 선정된 장르 내에서 재생수 기준으로 내림차순, 노래 고유 번호 기준으로 오름차순 정렬 한다.

4. 3 번에서 만들어진 데이터에서 앞의 두 개의 데이터를 추출하여 베스트 앰범에 넣는다.

 

 

 

코드

def solution(genres, plays):
    answer = []
    best = {}

    for song_number, genre in enumerate(genres):
        if not genre in best:
            best[genre] = [plays[song_number], [(song_number, plays[song_number])]]
        else:
            best[genre][0] += plays[song_number]
            best[genre][1].append((song_number, plays[song_number]))

    best_genres_sort = sorted(best.values(), key=lambda x:-x[0])

    for genre_play_info in best_genres_sort:
        rank_song = [play_info[0] for play_info in (sorted(genre_play_info[1],key = lambda x:(-x[1],x[0]))[:2]) ]
        answer.extend(rank_song)

    return answer