[코딩테스트] 프로그래머스 - 베스트앨범

1. 아이디어 

▪ 장르별 재생횟수 합계 구하기

▪ 장르별 노래리스트 만들기 (고유번호,재생횟수)

▪ 재생횟수 합계 기준 내림차순으로 장르 정렬하기

▪ for 문으로 재생횟수 합계 기준 내림차순으로 장르를 꺼내며 다음을 수행

   - 꺼낸 장르의 노래리스트를 (재생횟수, 고유번호) 기준 (내림차순, 오름차순)으로 정렬

   - 재생횟수가 가장 많은 2곡만 answer에 append

2. 시간복잡도

▪ O(N), N: 노래의 개수

3. 변수

▪ 장르별 재생횟수: dict(장르 : int)

▪ 장르별 노래리스트: dict(장르 : [(고유번호,재생횟수)])

Code

def solution(genres, plays):
    answer = []
    plays_sum = {}
    genres_plays = {} 
    
    for i, (genre, play) in enumerate(zip(genres, plays)):
    	# 장르별 재생횟수 더하기
        if genre not in plays_sum: 
            plays_sum[genre] = play 
        else:
            plays_sum[genre] += play 
        
        # 장르별 노래리스트 만들기
        if genre not in genres_plays:  
            genres_plays[genre] = [(i,play)]
        else:
            genres_plays[genre].append((i,play))
    
    # 장르별 재생횟수가 많은 순으로 정렬 
    plays_sum = sorted(plays_sum.items(), key=lambda x:x[1], reverse=True)
    
    # 선택된 장르별 재생횟수가 많은 2곡 찾기
    for genre, play in plays_sum:
        play_list = sorted(genres_plays[genre], key=lambda x:(x[1],-x[0]), reverse=True)
             
        for i, play in play_list[:2]:                          
            answer.append(i)
            
    return answer

 

프로그래머스