[프로그래머스] LV.3 베스트앨범 (Python) - 우선순위 큐 튜플 정렬

 

 

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

프로그래머스

소요시간: 30분

이렇게 알고리즘 뭐 쓰라고 써있는데도 한참 헤맬때 마음이 참 아프다. ^^

 

 

 

 

제출한 코드(통과는 되는데 함정이 있음)

import heapq
def solution(genres, plays):
    ans = []
    # 장르별로 2개씩
    # 순서: 1) 많이 재생된 장르(재생수 총합) 2) 장르 내에서는 많이 재생된 노래 먼저 3) if 하나면 하나만 수록하기
    genre_times = {g:[0,[]] for g in set(genres)}
    #{'장르이름':[총재생수, (-재생수:고유번호, -재생수:고유번호, ....)]}
    for i in range(len(plays)):
        genre_times[genres[i]][0] += plays[i]
        heapq.heappush(genre_times[genres[i]][1], (-plays[i], i))
    sorted_gt = dict(sorted(genre_times.items(), key=lambda x:x[1][0], reverse=True))
    for genre in sorted_gt:
        songs = sorted_gt[genre][1]
        cnt = 0
        while songs:
            if cnt == 2:
                break
            song = heapq.heappop(songs)
            ans.append(song[1])
            cnt += 1
    return ans

작성 의도 :

{'장르이름':[총재생수, (-재생수:고유번호, -재생수:고유번호, ....)]}

딕셔너리 genre_times 하나로 해결하기 위해 내부에 max heap을 구현했다. 

 

👀 heap의 원소가 튜플일 때는 튜플의 첫 번째 원소를 기준으로 최소 힙 정렬된다. 

이 문제에서는 최대 힙을 구현하기 위해서 흔히 쓰는 방법인 음의 부호(-) 붙이기를 사용했다.

고유 번호를 보존해서 리턴해야 했기 때문에 힙의 원소 튜플은 (-재생수, 고유번호) 로 구성.

 

 

 

 

여기서부터 공포 시작

일단 통과시키고 다시 뜯어봤는데 내가 조건을 하나 안 봤더라. 

장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다는 조건을 고려하지 않고 코드를 짰다.

근데 통과가 됐다.. 뭐야이거❤️

 

 

 

가만히 보니 내가 만든 최대 힙이 문제였다. 튜플의 두 번째 원소로도 정렬을 해야 하는 상황이었기 때문에, 통상적으로 힙을 쓰지 않는 유형의 문제였던 것이다.

그런데 왜 정답처리가 됐을까? 궁금해서 찾아봤다. 

 

https://docs.python.org/2/library/heapq.html

8.4. heapq — Heap queue algorithm — Python 2.7.18 documentation

 

if the priorites are equal and the tasks do not have a default comparison order 인 상황에는 튜플 비교가 불가능하다~ 는 말로 보인다. 

그 말인즉슨, 튜플로 구성된 우선순위 큐에서 priority가 같은 상황에, 튜플 원소의 두 번째 원소들에 default comparison order가 있다면 그대로 정렬되는 것이다.

보통 튜플의 첫 번째 원소 기준으로 우선순위가 정해진다~ 는 말만 나와있어서 더 알아볼 생각을 안 해봤는데, 사실은 이렇게 구현되어 있다고 한다. 

 

 

이 문제의 경우, 고유번호가 작은 순서대로 정렬이 필요했기 때문에 운좋게 조건과 맞아떨어진 것으로 보인다. 고유번호가 큰 순서대로였다면 고유번호에 마이너스 붙여서 삽입하면 됐을 것 같다.

 

 

소 뒷걸음치다 쥐 잡는 격으로 잘못 짠 코드로 최대 힙의 정렬에 대해 공부했다.

더 열심히 살아야겠다....... 화이팅