[프로그래머스 42579 파이썬] 베스트앨범 (level 3, 해시)

알고리즘 유형 : 해시
풀이 참고 없이 스스로 풀었나요? : O

https://programmers.co.kr/learn/courses/30/lessons/42579?language=python3

SOLVE 1

직접 푼 풀이

def solution(genres, plays):
    answer = []
    cluster = {}
    for idx in range(len(genres)):
        key = genres[idx]
        
        if key in cluster:
            cluster[key].append((idx, plays[idx]))
        else:
            cluster[key] = [(idx, plays[idx])]
    
    genres_sorted = []
    for key in cluster.keys():
        genres_sorted.append((key, sum([x[1] for x in cluster[key]])))
    genres_sorted = sorted(genres_sorted, key = lambda x: -x[1])
    
    for key, _ in genres_sorted:
        musics = sorted(cluster[key], key = lambda x: -x[1])
        
        for item in musics[:2]:
            answer.append(item[0])
    
    return answer

SOLVE 2

딕셔너리의 items()를 활용한 정렬과 enumerate, zip, defaultdict를 이용한 간결한 풀이

from collections import defaultdict

def solution(genres, plays):
    answer = []
    
    genres_order = defaultdict(int)
    genres_plays = defaultdict(list)
    
    for i, (genre, v) in enumerate(zip(genres, plays)):
        genres_order[genre] += v
        genres_plays[genre].append((i, v))
        
    for genre, _ in sorted(genres_order.items(), key = lambda x: x[1], reverse = True):
        for i, v in sorted(genres_plays[genre], key = lambda x: x[1], reverse = True)[:2]:
            answer.append(i)
    
    return answer

SOLVE 1) 풀이 요약 (직접 푼 풀이)

1. for를 돌면서, 장르 별로 노래의 고유번호를 같이 튜플로 묶어 딕셔너리에 저장한다.

2. 그 딕셔너리를 활용하여 장르 별 재생 횟수의 합을 튜플로 묶어 내림차순으로 정렬한 리스트를 구한다. (재생 횟수의 합에 따른 장르의 우선 순위 정보를 담고 있는 리스트)

3. 이 후 구한 리스트를 순회하면서, 각 키에 해당하는 밸류, 고유 번호와 곡 재생 횟수를 담은 튜플 리스트를 재생 횟수 기준 내림차순 정렬하고 두 번째 요소까지 answer에 append해준다.

SOLVE 2 풀이 요약 (딕셔너리의 items()를 활용한 정렬과 enumerate, zip, defaultdict를 이용한 간결한 풀이)

1. zip으로 장르와 곡 재생 횟수를 튜플로 묶어주고, 각각에 대한 고유번호를 enumerate로 구해준다.

2. 위를 for로 순회하면서, genres_order에는 장르 별(key) 총 재생 횟수를 key-value 쌍으로 저장하고, genres_plays에는 장르 별(key) (고유 번호, 재생 횟수)의 튜플 쌍을 저장한다.

   이 때 특정 키가 딕셔너리에 존재하지 않으면, genres_order의 경우 그 키의 밸류를 0으로 할당해주고 이어서 v를 더해주고, genres_plays의 경우 그 키의 밸류를 빈 리스트로 할당해주고 거기에 append 해주기 위해 defaultdict 모듈을 사용하여 코드를 간략하게 작성할 수 있다.

3. 이중 for문을 작성한다.

   genres_order의 items를, 두 번째 요소인 총 재생 횟수를 기준으로 내림차순 정렬한 것을 순회한다.

   그 안에서, 순회 중인 key(genre)에 대해 genres_plays[genre], 즉 (고유 번호, 재생 횟수) 튜플이 모여있는 리스트를 재생 횟수를 기준으로 내림차순 정렬한 것을 순회하며 고유 번호를 answer에 append해준다.

배운 점, 어려웠던 점

• 해시 문제에서 enumerate, zip, defaultdict를 언제 써먹어야 적재적소 활용이 되는지 경험을 쌓을 수 있었다. 더불어, items가 요소가 (key, value)인, iterable한 객체임을 알게 되었고, 리스트 슬라이싱이 리스트 길이보다 더 많이 자르게 지정해도 오류는 나지 않는다는 것을 알게 되었다.