프로그래머스 - 베스트 앨범

베스트 앨범

문제 설명

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

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한 사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

genres	plays	return
[classic, pop, classic, classic, pop]	[500, 600, 150, 800, 2500]	[4, 1, 3, 0]

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

설명

해시를 이용하는 문제입니다. 파이썬의 딕셔너리를 이용해 풀이합니다. 파이썬의 딕셔너리는 key: value로 이루어져 있는 자료구조로, 배열처럼 index로 값을 참조하는 게 아니라 특정한 key값에 해싱 함수를 적용해 value를 찾아가도록 합니다. key는 숫자일 수도 있고 문자, 문자열일 수도 있습니다.

풀이

먼저 2가지를 생각해보겠습니다.

1. 어떤 장르가 제일 많이 재생되었는가
2. 장르에서 재생시간 상위 2곡을 어떻게 뽑아낼것인가

1. 어떤 장르가 제일 많이 재생되었는가

사실 어떤 장르가 제일 많이 재생되었는지는 간단합니다. 반복문을 돌려가며 딕셔너리에 key : 장르, value : 재생시간의 형태로 저장한 뒤 재생시간이 정렬만 된다면 순서를 알아낼 수 있습니다.

문제는 딕셔너리가 정렬을 지원하지 않는다는 점입니다.

저는 제한사항의 모든 장르는 재생된 횟수가 다릅니다.사항을 이용해 key : 장르, value : 재생시간형태로 저장한 딕셔너리를 key : 재생시간, value : 장르로 따로 저장한 뒤 재생시간만 따로 리스트로 뽑아내 정렬, 가장 재생시간이 긴 시간부터 key로 시간을 참조해 value로 장르를 뽑아내는 방식으로 가장 시간이 긴 장르를 뽑아냈습니다.
전체 코드입니다.

def solution(genres, plays):
    answer = []
    music_dict = {} # key : 장르, value : 총 재생시간
    music_dict_reverse = {} # key : 재생시간, value : 장르
    play_dict = {} # key : 장르, value : 번호별 곡 재생시간(각각을 [재생시간, 번호]로 저장)

    for k in range(len(genres)):
        music_dict[genres[k]] = music_dict.get(genres[k], 0) + plays[k]
        play_dict[genres[k]] = play_dict.get(genres[k], []) + [[plays[k], 10000-k]]

    for key, values in music_dict.items():
        music_dict_reverse[values] = key # key와 value reverse

    total_list = sorted(list(music_dict.values()), reverse = True) # 재생시간만 내림차순 정렬

    for total in total_list:
        key = music_dict_reverse[total]
        genre_total_list = sorted(play_dict[key], reverse = True)
        n = 0
        end = 2 if len(genre_total_list) > 1 else 1
        while n < end:
            answer.append(10000 - genre_total_list[n][1])
            n += 1

    return answer

 

2. 장르에서 재생시간 상위 2곡을 어떻게 뽑아낼 것인가

저장을 위한 딕셔너리 하나를 더 만들고 총 재생시간과 재생된 곡들을 각각 다른 딕셔너리에 저장했습니다.

play_dict = {} # key : 장르, value : 번호별 곡 재생시간(각각을 [재생시간, 번호]로 저장)

# 예시 (이러한 형태로 저장되어 있음)
play_dict = {
    'classic' : [[500, 10000], [600, 9999], [700, 9998]],
    'pop': [[1600, 9997], [5000, 9996]]
} 

이 딕셔너리에는 총 재생시간이 아니라 [곡의 재생시간, 곡 번호] 의 형태로 리스트가 추가되며, 문제 설명의

• 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

항목에 따라서, 재생시간 : 내림차순(우선순위) -> 번호 : 오름차순으로 정렬해야 합니다.

내림차순으로 통일하기 위해, 번호를 10000-k로 저장해 가장 작은 번호가 가장 큰 값을 가지도록 합니다.

play_dict[genres[k]] = play_dict.get(genres[k], []) + [[plays[k], 10000-k]]

가장 재생시간이 긴 장르를 뽑아낸 뒤, 상위 2곡을 뽑아냅니다. 문제 설명의

• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.

항목에 따라 1곡만 있을 경우에는 1곡만 선택합니다.

for total in total_list:
    key = music_dict_reverse[total] # 시간에서 장르 추출
    genre_total_list = sorted(play_dict[key], reverse = True) # 장르의 모든 노래번호와 재생시간이 [[500, 10000], [600, 9999], [700, 9998]] 형태로 저장되어 있음
    n = 0
    end = 2 if len(genre_total_list) > 1 else 1 # 장르에 속한 곡이 하나라면 하나만 선택하도록
    while n < end:
        answer.append(10000 - genre_total_list[n][1]) #번호를 10000-k 형태로 저장했기 때문에 원래 번호인 10000-k를 answer에 추가
        n += 1

정리 (예시)

def solution(genres, plays):
    answer = []
    music_dict = {}
    music_dict_reverse = {}
    play_dict = {}

    for k in range(len(genres)):
        music_dict[genres[k]] = music_dict.get(genres[k], 0) + plays[k]
        play_dict[genres[k]] = play_dict.get(genres[k], []) + [[plays[k], 10000-k]]

    for key, values in music_dict.items():
        music_dict_reverse[values] = key

    total_list = sorted(list(music_dict.values()), reverse = True)

    for total in total_list:
        key = music_dict_reverse[total]
        genre_total_list = sorted(play_dict[key], reverse = True)
        n = 0
        end = 2 if len(genre_total_list) > 1 else 1
        while n < end:
            answer.append(10000 - genre_total_list[n][1])
            n += 1

    return answer