베스트앨범-LV3

- 문제

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

 

코딩테스트 연습 - 베스트앨범 | 프로그래머스 스쿨

프로그래머스

 

- 키포인트

해시 정렬 방법

a = [(1, 2), (5, 1), (0, 1), (5, 2), (3, 0)]

c = sorted(a, key = lambda x : x[0]) 

c = [(0, 1), (1, 2), (3, 0), (5, 1), (5, 2)]

d = sorted(a, key = lambda x : x[1]) 

d = [(3, 0), (5, 1), (0, 1), (1, 2), (5, 2)]

 

여러개 정렬 시 튜플형태로 우선순위 가능, - 붙이면 내림차순

e = sorted(a, key = lambda x : (x[0], -x[1])) 
=> [(0, 1), (1, 2), (3, 0), (5, 2), (5, 1)]

f = sorted(a, key = lambda x : -x[0]) 
=> [(5, 1), (5, 2), (3, 0), (1, 2), (0, 1)])

 

문자열도 정렬 가능

s = ['2 A', '1 B', '4 C', '1 A']
s.sorted(s, key=lambda x: (x.split()[1], x.split()[0]))
=> ['1 A', '2 A', '1 B', '4 C']
a_list = ['a', 'b', 'd', 'd', 'b','s']
a_counter = Counter(a_list).most_common()
=> [('b', 2), ('d', 2), ('a', 1), ('s', 1)]

# 문자 역순(아스키 값 이용)
sorted(a_counter,  key=lambda x: (-x[1], -ord(x[0])))
=> [('d', 2), ('b', 2), ('s', 1), ('a', 1)]

 

- 코드

from collections import defaultdict

def solution(genres, plays):
    genre_map=defaultdict(list)
    answer = []
    # 장르 해시맵 생성
    for idx, (genre, play) in enumerate(zip(genres, plays)):
        genre_map[genre].append((play,idx))
    # 장르별 플레이합 해시 생성
    genre_sum={}
    for genre, play_list in genre_map.items():
        total_play=0
        # 첫번째값(플레이수)만 계산
        for play, _ in play_list:
            total_play+=play
        genre_sum[genre]=total_play
    # 장르별 플레이수합 내림차순 정렬    
    genre_sum_sort=sorted(genre_sum.keys(), key=lambda genre:genre_sum[genre],reverse=True)
    # 장르별 플레이수 기준 내림차순 정렬, 같은 재생횟수이면 인덱스 기준 오름차순 정렬
    for genre in genre_sum_sort:
        top_songs = sorted(genre_map[genre], key=lambda x: (-x[0],x[1]))
        # 최대 2곡까지만 추가
        count=0
        for play, idx in top_songs:
            answer.append(idx)  
            count+=1
            if count==2:
                break
    return answer

def solution(genres, plays):
    answer = []
    total_play = {} # {장르: 총 재생 횟수}
    genre_idx = {} # {장르: [(플레이 횟수, 고유번호)]}

    for i in range(len(genres)):
        total_play[genres[i]] = total_play.get(genres[i], 0) + plays[i]
        genre_idx[genres[i]] = genre_idx.get(genres[i], []) + [(plays[i], i)]
    # total_play : 	{'classic': 1450, 'pop': 3100}
    # genre_idx : {'classic': [(500, 0), (150, 2), (800, 3)], 'pop': [(600, 1), (2500, 4)]}
	# 재생 횟수 내림차순으로 장르별 정렬
    genre_idx_sort = sorted(total_play.items(), key=lambda x: x[1], reverse=True)

	# 재생 횟수 내림차순, 인덱스 오름차순 정렬
    for (genre, totalPlay) in genre_idx_sort:
        genre_idx[genre] = sorted(genre_idx[genre], key=lambda x: (-x[0], x[1]))
        answer += [idx for (play, idx) in genre_idx[genre][:2]]
        
    return answer