[프로그래머스] 더 맵게

min heap에서 2가지 원소를 pop 하고 a + 2 * b 의 등식을 적용 후 push 하는 문제였다.

파이썬의 heapq를 처음 사용해보았다.

• 파이썬의 heapq의 경우 일반 리스트를 min heap 처럼 사용할 수 있게 해주는 라이브러리이다.
• heapq.heapify(list): list가 min heap으로 변한다. (O(N), 제자리에서 정렬)
• heapq.heappop(list): heapify된 list에서 min 값을 리턴.
• heapq.heappush(list, item)
  • push의 경우 이론에서 배웠던 heapify를 자동으로 수행해준다.
  • 0번 인덱스에는 가장 작은 값, n번 인덱스의 2n + 1 인덱스에는 left child, 2n + 2 인덱스에는 right child ( parent <= left, right child )

import heapq
import collections
def solution(scoville, K):
    c = collections.Counter(scoville)

    # 기존 리스트를 힙으로 변환
    heapq.heapify(scoville)

    # 우리가 원하는 맵기까지 만들지 못하고, 힙의 길이가 2 이상인 경우 새로운 음식 만들기.
    cnt = 0
    while scoville[0] < K and len(scoville) >= 2:
        smallest = heapq.heappop(scoville)
        next_small = heapq.heappop(scoville)
        heapq.heappush(scoville ,smallest + 2 * next_small)
        cnt += 1

    # 힙의 길이가 1이 되어버리고, 원하는 맵기까지 도달 못한 경우
    if len(scoville) < 2 and scoville[0] < K:
        return -1

    return cnt

 

 

효율성 테스트

 

테스트 1 〉	통과 (191.62ms, 23.8MB)
테스트 2 〉	통과 (382.37ms, 37.5MB)
테스트 3 〉	통과 (2037.07ms, 80.1MB)
테스트 4 〉	통과 (152.45ms, 22.2MB)
테스트 5 〉	통과 (2082.18ms, 82.2MB)