문제 설명
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
속한 노래가 많이 재생된 장르를 먼저 수록합니다.
장르 내에서 많이 재생된 노래를 먼저 수록합니다.
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 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] 번 노래를 그다음에 수록합니다.
문제 풀이 - Hash Table, 해시, 딕셔너리
해시를 사용하는 문제이기 때문에 파이썬의 딕셔너리를 사용해서 문제를 풀었습니다
우선 딕셔너리에 입력을 사용하기 좋게 저장했습니다.
key는 장르이고 value는 이차원 배열로 각 배열은 노래 재생 횟수와 노래 고유 번호로 저장됩니다.
형식 : { 장르1: [[노래 1 재생 횟수 :노래 1 고유 번호], [노래 2 재생 횟수: 노래 2 고유번호]...]}
그리고 첫번째 기준인 "속한 노래가 많이 재생된 장르를 먼저 수록"을 충족하기 위해서 많이 재생된 장르 순으로 딕셔너리를 만들었습니다.
딕셔너리에 각 장르의 모든 곡의 총 재생 횟수 저장하고 이를 정렬하였습니다.
형식 : {장르 1 : 모든 장르 1곡의 총 재생 횟수 ,장르 2 : 모든 장르 2곡의 총 재생 횟수...}
그리고 마지막으로 위의 두 딕셔너리를 사용하여 정렬과 동시에 answer 리스트에 노래의 아이디 저장을 반복합니다.
def solution(genres, plays):
answer = []
#dic 딕셔너리에 입력 저장- { 장르1: [[노래1 재생 횟수 :노래1 고유 번호],[노래2 재생 횟수: 노래2 고유번호]...]} 형식으로
dic={}
for i in range(len(genres)):
if genres[i] in dic:
dic[genres[i]].append([plays[i],i])
else :
dic[genres[i]] = [[plays[i],i]]
#genre_rank 딕셔너리에 각 장르의 모든 곡의 총 재생 횟수 저장- {장르 1 : 모든 장르 1곡의 총 재생 횟수 ,장르 2 : 모든 장르 2곡의 총 재생 횟수...}
genre_rank ={}
for genre in dic.keys():
songs = dic[genre]
plays_sum = 0
for song in songs:
plays_sum+=song[0]
genre_rank[genre] = plays_sum
#genre_rank를 재생 횟수가 큰 순으로 정렬
genre_rank = sorted(genre_rank.items(), key=lambda x: x[1],reverse=True)
# genre_rank에 저장되어 있는 장르 순으로 dic에서 해당 장르를 key로 가진 value를 확인
for genre in genre_rank:
#2차원 배열인 value를 다중 조건으로 정렬 (첫번째 인자인 곡 재생 수를 기준으로 내림차순 정렬 후,
# 두번째 인자인 곡 고유 번호를 기준으로 오름차순 정렬)
song_rank=sorted(dic[genre[0]], key=lambda x:(-x[0],x[1]))
best_two = 0
# 정렬된 배열을 하니씩 확인하면서 answer에 고유 번호를 순서대로 저장 , 만약 한 장르의 곡이 두 곡 저장되면 해당 장르에서 반복 중지
for song in song_rank:
answer.append(song[1])
best_two +=1
if best_two == 2:
break
return answer
문제를 제대로 읽지 않고 바로 문제를 풀다보니 삽질을 여러 번 했습니다.
우선 장르 별로 가장 많이 재생된 노래 ->
classic 장르는 1,450회 재생,pop 장르는 3,100회 재생으로 pop classic 순이여함
근데 나는 classic 장르 3곡 pop 장르 2곡이니까 classic, pop 순이라고 잘못 이해
암튼 그래서 다음부터는 문제를 꼭 꼼꼼히 읽고
반드시 입출력 예를 확실히 이해하고 구현 시작해야겠습니다.
