[프로그래머스] 베스트앨범
문제
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
- 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
- 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
- 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 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] |
풀이
해쉬 카테고리에 속하는 문제로 장르별 총 재생횟수와, 장르별 노래들의 재생횟수와 인덱스를 잘 저장하고 정렬하여 써먹어야 하는 문제이다.
나는 먼저 장르별 재생횟수를 Dictionary에 저장하였고, 이 Dictionary를 사용하여 장르별 총 재생횟수가 저장된 리스트를 만들어낸 다음 총 재생횟수가 높은 장르의 노래들부터 차트answer에 추가하는 방법으로 이 문제를 해결하였다.
차트에 추가할 때 장르별 노래 재생횟수와 인덱스를 정렬하는 부분에서 까다롭긴 한데 sorted함수의 key 인자로 lambda함수를 만들어 넣는 방법으로 해결이 가능하였다.
gen_each[gen] = sorted(gen_each[gen], key=lambda x: (x[0], -x[1]))에서 gen_each[gen]은 gen에 따른[[재생횟수, idx], ...]가 저장되어 있다.
key=lambda x: (x[0], -x[1])의 뜻은 재생횟수에 대해서는 오름차순으로, idx에 대해서는 내림차순으로 정렬하라는 것을 의미한다.
전체 Flow를 정리하면 아래와 같다.
- answer는 노래가 추가될 앨범,
gen_total은 genres와 genres에 따른 총 재생횟수로 이루어진 1차원 배열이 저장될 2차원 배열,gen_each는 genres가 key이고, 그 value는 같은 장르인 곡의 재생횟수와 인덱스로 이루어진 1차원 배열들이 저장된 2차원 배열이다. gen_each를 생성하고,gen_each의 재생횟수를 모두 더해 각 genres별 총 재생횟수를gen_total에 저장한다.gen_total을 총 재생횟수에 따라 내림차순으로 정렬한다.- total_p와 gen은 gen_total의 i번째 성분으로, 각각 총 재생횟수와 장르를 의미한다.
gen_each[gen]을 재생횟수에 따라서는 오름차순으로, 인덱스를 따라서는 내림차순으로 정렬한다.gen_each[gen]의 성분을 pop하고 해당 idx를 answer에 추가한다.- 6을
gen_each[gen]의 성분이 없거나 두번의 차트 입력이 끝날 때 까지만 반복한다. - 4~7을 전체 genres에 대해서 반복한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def solution(genres, plays):
answer = []
# [[총 재생횟수, genres], ...,[총 재생횟수, genres]]
gen_total = []
# {genres: [[재생횟수, idx], .. [재생횟수, idx]]}
gen_each = {}
for i, (g, p) in enumerate(zip(genres, plays)):
if g in gen_each:
gen_each[g].append([p, i])
else:
gen_each[g] = [[p, i]]
for key in gen_each:
#value = [재생횟수, idx]
total = 0
for play, idx in gen_each[key]:
total += play
# [[총 재생횟수, genres]]
gen_total.append([total, key])
gen_total = sorted(gen_total, reverse=True)
print(gen_total)
for total_p, gen in gen_total:
# gen_total은 내림차순으로 정렬된 배열
t = 0
gen_each[gen] = sorted(gen_each[gen], key=lambda x: (x[0], -x[1]))
# 재생횟수는 오름차순으로 정렬한 것을 기준으로 인덱스는 내림차순으로 정렬됨
while gen_each[gen] and t < 2:
# 장르에 따른 곡이 이제 없거나, 두번의 차트 입력이 끝날 때 까지 반복
play, idx = gen_each[gen].pop()
answer.append(idx)
t += 1
return answer