[Programmers][힙(Heap)] 더 맵게 python (211027)

코딩테스트 연습 - 더 맵게

이해도

★★★☆☆

소감

힙 자료구조에 대해 알게되었다. 

파이썬 힙큐(heapq) 모듈을 사용하여 구현하는 방법을 알게 되었다.

 

힙을 만드는 방법

방법 1. 빈 리스트 생성 후 heappush 함수로 넣기

방법 2. heapify 함수로 리스트를 바로 힙으로 바꾸기

 

-> 처음에 이 두 개를 같이 써서 시간초과가 났었다. heapify 사용할 경우, 새로운 변수에 넣는게 아니라 리스트를 힙 자체로 변환한다는 점에 주의하자!

 

• heapify 하면 기존 리스트를 바로 힙으로 변환한다.
• heappush 를 하면 아이템이 힙에 들어가는데, 자동적으로 가장 작은 숫자가 맨 앞으로 간다.
• heappop 을 하면 힙에서 가장 작은 아이템을 반환하며, 이는 heap[0] 과도 같다.
• heappushpop 도 있는데 효율적이라고 한다.

 

파이썬 공식 홈페이지(링크)

from heapq import heapify, heappush, heappop

def solution(scoville, K):
    answer = 0
    
    # 방법1 heapq.heapify(x) 리스트 x를 선형 시간으로 제자리에서 힙으로 변환
    heapify(scoville)

    # 방법2 heapq.heappush(heap, item)
    h = []
    for food in scoville:
        heappush(h, food)

    # scoville의 길이는 2 이상이다.
    while len(scoville) >= 2:
            f1 = heappop(scoville)
            f2 = heappop(scoville)
            heappush(scoville, f1 + f2 * 2)
            answer += 1

            # 스코빌 최소값이 K 이상이면
            if scoville[0] >= K:
                return answer

    return -1