[프로그래머스] 베스트앨범 (Python)

https://programmers.co.kr/learn/courses/30/lessons/42579

코딩테스트 연습 - 베스트앨범

충분히 풀 수는 있지만 뭔가 코드가 효율적이지 않은 것 같은 느낌이 드는 풀이였다. 시간 복잡도는 O(N)이라 나쁘지 않을 수도?

 

1. 장르별로 값을 dict에 초기화해주고, 판매수는 큰 순으로, 같을 때 고유 번호는 작은 순으로 정렬한다.

2. 각 장르별로 총판매수를 구하고, 총판매수가 큰 순으로 장르를 정렬한다.

3. 판매수가 큰 장르부터 두 개씩 뽑아서 고유번호를 정답에 추가해준다(단, 장르의 판매수가 하나일 때는 하나만 추가)

 

나의 풀이

from collections import defaultdict
def solution(genres, plays):
    album = defaultdict(list)
    num = []
    answer = []
    for i in range(len(genres)):
        album[genres[i]].append([plays[i],i])
    for key in album.keys():
        album[key].sort(key = lambda x: (-x[0],x[1]))
    for key,value in album.items():
        num_sum = 0
        for v in value:
            num_sum +=v[0]
        num.append([key,num_sum])
    num.sort(key = lambda x: -x[1])
    for genre,_ in num:
        if len(album[genre]) ==1:
            answer.append(album[genre][0][1])
        else:
            answer.append(album[genre][0][1])
            answer.append(album[genre][1][1])
    return answer