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

문제

문제 보러가기 >> [프로그래머스] 베스트앨범

풀이요약

1. genre를 key, value는 (genre내 모든 곡들의 total play수, [(play수,곡번호),(play수,곡번호)])

   • [(play수,곡번호),(play수,곡번호)] 부분은 우선순위큐를 이용한다.

   • PriorityQueue, heaqp 모두 오름차순이 default이므로 내림차순을 위해 *-1

   • ex) {'classic':(-1450, [(-800, 3), (-150, 2), (-500, 0)]), 'pop': (-3100, [(-2500,4),(-600,1)])}

2. Total play 수에 따라 genre 정렬 => sorted(genreHash.values())

   • [(-3100, [(-2500, 4), (-600, 1)]), (-1450, [(-800, 3), (-150, 2), (-500, 0)])]

3. 각 장르내에서 우선순위에 따라 2개씩 뽑아서 answer에 저장

   • 한곡만 있는 경우도 생각하자.

4. answer 출력

시도

첫번째 시도 - PriorityQueue

• PriorityQueue, dict를 사용

  heapq와 PriorityQueue 중에서 PriorityQueue 를 사용한 이유는 .. 정말 단순하게도 이름이 내가 원하는 기능에 직관적으로 와닿았달까..... '우.선.순.위.큐' 직역...( ..).. 아직 많이 부족하다.

• BUT 시간초과

from queue import PriorityQueue
    
def solution(genres, plays):
    answer = []
    genreHash = {}
    
    #풀이 1 genreHash 만들기
    for i, (genre, play) in enumerate(zip(genres,plays)):
        if genre not in genreHash:
            genreHash[genre] = (0, PriorityQueue())
        genreHash[genre][1].put((-play, i))	
        genreHash[genre] = ( genreHash[genre][0]-play,  genreHash[genre][1])

     #풀이2 totalplay 수에 따른 genre 정렬
    res = sorted(genreHash.values())
    
    for album in res:
        answer.append(album[1].get()[1])
        if(album[1]):
            answer.append(album[1].get()[1])

    return answer

테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 통과 (0.04ms, 10.5MB)
테스트 4 〉 실패 (시간 초과)
테스트 5 〉 통과 (0.30ms, 10.4MB)
테스트 6 〉 통과 (0.58ms, 10.5MB)
테스트 7 〉 통과 (0.21ms, 10.5MB)
테스트 8 〉 실패 (시간 초과)
테스트 9 〉 실패 (시간 초과)
테스트 10 〉 통과 (0.31ms, 10.5MB)
테스트 11 〉 실패 (시간 초과)
테스트 12 〉 실패 (시간 초과)
테스트 13 〉 통과 (0.27ms, 10.4MB)
테스트 14 〉 통과 (0.31ms, 10.4MB)
테스트 15 〉 통과 (0.07ms, 10.4MB)

두번째 시도 - heapq

• heapq, dict를 사용하여 성공!

import heapq
def solution(genres, plays):
    answer = []
    genreHash = {}

    for i, (genre, play) in enumerate(zip(genres,plays)):
        if genre not in genreHash:
            genreHash[genre] = (0, [])

        heapq.heappush(genreHash[genre][1], (-play, i))
        genreHash[genre] = ( genreHash[genre][0] - play,  genreHash[genre][1])
   
    res = sorted(genreHash.values())

    for album in res:
        answer.append(heapq.heappop(album[1])[1])
        if(album[1]):
            answer.append(heapq.heappop(album[1])[1])

    return answer

성공!
테스트 1 〉 통과 (0.02ms, 10.2MB)
테스트 2 〉 통과 (0.02ms, 10.2MB)
테스트 3 〉 통과 (0.01ms, 10.2MB)
테스트 4 〉 통과 (0.01ms, 10.2MB)
테스트 5 〉 통과 (0.11ms, 10.2MB)
테스트 6 〉 통과 (0.08ms, 10.4MB)
테스트 7 〉 통과 (0.05ms, 10.2MB)
테스트 8 〉 통과 (0.04ms, 10.3MB)
테스트 9 〉 통과 (0.02ms, 10.3MB)
테스트 10 〉 통과 (0.10ms, 10.3MB)
테스트 11 〉 통과 (0.02ms, 10.2MB)
테스트 12 〉 통과 (0.05ms, 10.3MB)
테스트 13 〉 통과 (0.09ms, 10.3MB)
테스트 14 〉 통과 (0.09ms, 10.3MB)
테스트 15 〉 통과 (0.02ms, 10.2MB)

결론

우선순위큐를 사용하고자 할 때, heapq 와 PriorityQueue 중에서 heapq를 사용하는 것이 속도면에서 유리하다.

그렇다면, PriorityQueue는 굳이 왜 만들었을까? 둘의 차이는 무엇이고, 어떻게 구분해서 사용해야할까?

정리해보자 > heapq와 PriorityQueue

+)heapq, PriorityQueue 사용팁!

튜플 사용시 첫번째 인자가 같으면 두번째 인자로, 두번째 인자가 같으면 세번째 인자로 .... n-1번째 인자까지 같으면 n번째 인자로 정렬된다.

즉, SQL의 ORDER BY play, songId 처럼 사용할 수 있다. 이 문제처럼 두가지 이상의 우선순위가 필요하다면 매우 유용하니 기억해두자.

heap

test = []
heapq.heappush(test, (50, 4, 1))
heapq.heappush(test, (100, 3, 0))
heapq.heappush(test, (100, 1, 0))
heapq.heappush(test, (100, 2, 1))
heapq.heappush(test, (100, 2, 2))
heapq.heappush(test, (100, 2, 0))

while(test):
    print(heapq.heappop(test))

#결과
#(50, 4, 1)
#(100, 1, 0)
#(100, 2, 0)
#(100, 2, 1)
#(100, 2, 2)
#(100, 3, 0)

PriorityQueue

test2 = PriorityQueue()
test2.put((50, 4, 1))
test2.put((100, 3, 0))
test2.put((100, 1, 0))
test2.put((100, 2, 1))
test2.put((100, 2, 2))
test2.put((100, 2, 0))

while(test2):
    print(test2.get())
    
#결과
#(50, 4, 1)
#(100, 1, 0)
#(100, 2, 0)
#(100, 2, 1)
#(100, 2, 2)
#(100, 3, 0)