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

💡문제 링크

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

프로그래머스

 

 

 

💡문제 분석 요약

정렬과 해싱을 이용하는 문제

1. 장르 정렬: 재생횟수가 가장 많은 장르순으로 정렬

2. 장르 내 노래 정렬: 하나의 장르 내에서 재생횟수가 가장 많은 노래순으로 정렬해서 노래 2개 선택, 재생횟수가 동일하면 고유번호가 작은 노래가 앞에 오도록 정렬

3. 장르별로 가장 많이 재생된 노래를 두개씩 뽑아 베스트앨범에 넣기

 

💡알고리즘 설계

1. 장르별 재생횟수 정보를 담은 딕셔너리를 만든 뒤, 재생횟수가 가장 많은 장르순으로 정렬

for i in range(len(genres)):
    g, p = genres[i], plays[i]
    if g not in music_count:
        music_count[g] = 0
    music_count[g] += p
genres_sorted = sorted(music_count.items(), key = lambda x: x[1], reverse = True)

2. 장르별로 재생횟수가 가장 많은 노래순으로 정렬, 재생횟수가 동일하면 고유번호가 작은 게 앞에 오도록.

music = {}
for genre in genres_sorted:
    music[genre[0]] = []
for i in range(len(genres)):
    g, p = genres[i], plays[i]
    music[g].append([i, p])

3. 장르별로 두 개의 노래만 answer 리스트에 넣기

answer.extend([x[0] for music_info in music.values() for x in sorted(music_info, key=lambda x: (-x[1], x[0]))[:2]])

4. 리스트 반환

 

이를 해결하기 위해 music_count와 music 딕셔너리를 만들었다.

1. music_count : 장르별 재생횟수를 담은 딕셔너리

{'classic': 2900, 'pop': 6200, 'jazz': 6200}

-> 나중에 genres_sorted 리스트에다가 재생횟수가 많은 장르순으로 정렬해서 넣음

genres_sorted = sorted(music_count.items(), key = lambda x: x[1], reverse = True)

[('pop', 6200), ('jazz', 6200), ('classic', 2900)]

자료구조를 딕셔너리에서 리스트로 바꾼 다음에 정렬하는 이유: 딕셔너리는 정렬 불가능. 따라서 sorted(딕셔너리명.items(), 정렬기준, 매개변수 reverse)를 사용해야 함 

2. music: 장르별로 [고유번호, 재생횟수]를 담음. 물론 key값의 순서는 위에서 정렬한대로 재생횟수 많은 장르순.

{'pop': [[5, 2500], [13, 2500], [1, 600], [9, 600]], 'jazz': [[7, 1100], [15, 1100], [2, 1000], [6, 1000], [10, 1000], [14, 1000]], 'classic': [[4, 800], [12, 800], [0, 500], [8, 500], [3, 150], [11, 150]]}

 

💡코드

def solution(genres, plays):
    music_count = {}
    answer = []
    # 재생횟수가 가장 많은 장르순으로 정렬
    for i in range(len(genres)):
        if genres[i] not in music_count:
            music_count[genres[i]] = 0
        music_count[genres[i]] += plays[i]
    genres_sorted = sorted(music_count.items(), key = lambda x: x[1], reverse = True)

    # 장르별 고유 번호와 재생 횟수를 담은 딕셔너리 music 생성
    music = {}
    for genre in genres_sorted:
        music[genre[0]] = []
    for i in range(len(genres)):
        g, p = genres[i], plays[i]
        music[g].append([i, p])

    # 장르 내에서 많이 재생된 노래를 먼저 수록
    answer.extend([x[0] for music_info in music.values() for x in sorted(music_info, key=lambda x: (-x[1], x[0]))[:2]])


    return answer

 

💡 오답 풀이

1. 처음에 장르를 재생횟수로 정렬하는 거에서 막혔다. 그냥 일단 장르 정렬하고, 그 다음에 노래 정렬했다.

2. 해싱 유형이다보니 리스트에서 인덱스를 활용해서 값을 불러오는 경우가 많았다. 그래서 인덱스별로 헷갈렸다. 

3. 장르 내에서 많이 재생된 노래를 먼저 수록하는 코드는 원래 이랬다.

# 장르 내에서 많이 재생된 노래를 먼저 수록
for music_info in music.values():
    music_info.sort(key=lambda x: (-x[1], x[0]))
    answer.append(music_info[0][0])
    answer.append(music_info[1][0])

근데 이것때문인지 자꾸 일부 케이스에서 런타임에러 떠서 53.3 / 100이 떴다.

이걸 해결하기 위해서 chatGPT의 힘을 빌려 한 줄로 바꿨다.

answer.extend([x[0] for music_info in music.values() for x in sorted(music_info, key=lambda x: (-x[1], x[0]))[:2]])

💡 다른 풀이

...molar

 

💡 느낀점 or 기억할정보

1. 정렬할 때 lambda 쓰는 거 어렵다..정렬 기준이 두 개일 때는 ()로 감싸기, 하나는 오름차순이고 하나는 내림차순이면 기준 앞에 - 붙여서 정렬순서 바꾸기   

2. 딕셔너리를 정렬할 때에는 리스트로 변환한 뒤 정렬!
sorted(딕셔너리명.items(), 정렬기준, 매개변수 reverse)