프로그래머스 | 해시 - 베스트앨범 (python)

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

프로그래머스

 

🔅 문제 접근

상단과 같이 가장 많이 재생된 장르를 고르고, 해당 장르에서 많이 재생된 노래를 2개씩 차례로 수록하는 문제다.

단, 수록된 노래가 하나라면 하나의 곡만 선택하고 재생횟수가 같은 노래의 경우 고유번호 순으로 출력한다.

 

카테고리별로 노래를 분류한 뒤, 다중 조건을 걸어 노래를 출력해야 한다.

다중 조건을 쉽게 걸고, 또 시간 복잡도를 줄일 수 있는 방법으로 heap가 생각났다.

 

(1) 카테고리별로 분류를 할 때 카테고리 총 재생횟수를 저장하고, heapq에 노래의 재생횟수와 고유번호를 넣는다 (재생횟수 내림차순 고유번호 오름차순 정렬)

(2) 카테고리 총 재생횟수 내림차순으로 정렬한다.

(3) 각 카테고리를 for문으로 순회하며 heapq의 상단에 있는 것 2개 (1개일 경우 1개)를 정답 배열에 넣는다.

 

🔅 문제 풀이

import heapq

def solution(genres, plays):
    answer = []
    
    #1 - 카테고리별 총합 카운트, 재생횟수와 고유번호 힙 저장
    d = {}
    
    for g, p, i in zip(genres, plays, range(len(genres))):
        if d.get(g) is None:
            d[g] = [p, [(-p, i)]]
        else:
            d[g][0] += p
            heapq.heappush(d[g][1], (-p, i))
    
    #2 - 카테고리별 재생횟수를 기준으로 내림차순 정렬
    sorted_g = sorted(list(d.values()), key = lambda x : x[0], reverse = True)
    
    #3 - 각 카테고리 별로 for문으로 순회하며 heapq 상단 두개 정답 배열에 삽입  
    for s in sorted_g:
        answer.append(heapq.heappop(s[1])[1])
        
        if s[1]:
            answer.append(heapq.heappop(s[1])[1])
    
    return answer

 

 다음과 같이 heapq를 사용하여 이중 정렬을 하였다.

 

"카테고리" : [ 카테고리 총합, [(재생수1, 고유번호1),(재생수1, 고유번호2), ... ]  ]

 

위와 같이 카테고리 항목의 첫번째 값은 카테고리의 총합, 두번째 값은 각 카테고리의 노래가 조건에 맞게 정렬되어 있는 heapq이다.

 

시간복잡도 O(log k)의 힙 정렬을 n번 수행하므로, 시간복잡도는 대략 O(n log k)이다. (k는 장르 내 곡수, n은 카테고리 수)

 

다른 코드의 경우 이중 정렬을 사용하는데, heapq를 수행할 경우 이렇게 두번 정렬을 수행할 필요 없이 한번에 재생 횟수의 내림차순과 고유 번호 오름차순을 동시에 만족하는 정렬이 가능하기 때문에 보다 효율적이다.

 

아, 그리고 heapq로 정렬을 수행할 때 -를 붙인 부분이 있는데, 이 부분은 내림차순 정렬을 한다는 의미다. 정렬을 하고 싶은 최우선 조건부터 heapq의 맨 앞 인자로 삽입하고, 오름차순인지 내림차순인지는 부호를 통해서 결정하면 된다.

 

물론, 내림차순 정렬 후 값을 사용할 때는 다시 부호를 반전시키는 과정이 필요할 것이다.

🔅 배운점 및 느낀점

 heapq를 사용한다는 아이디어 자체는 스스로 생각해냈지만, heapq 사용법이나 이중 조건 정렬을 위한 방법 들은 인터넷을 검색하여 참고하였다. 문제를 많이 풀어서 이런 사소한 문법적인 부분은 생각하지 않아도 바로 나올 수 있도록 하는 것이 좋을 것 같다.

 

 그리고 이렇게 다른 사람들이 어떻게 풀었는지를 비교함으로써 다음에 다른 문제를 풀 때에도 다양한 문제 풀이를 얻을 수 있을 것 같다. 앞으로도 효율적이고, 잘 읽히는 좋은 코드로  (빨리 ,,, ) 문제를 해결해봐야지.