Programmers / 2단계 / [힙(Heap)] 더 맵게 / python /

코딩테스트 연습 - 더 맵게 | 프로그래머스 스쿨 (programmers.co.kr)

 

나의 풀이 

.

 

 

모범 답안

import heapq as hq

def solution(scoville, K):

    hq.heapify(scoville)
    answer = 0
    while True:
        first = hq.heappop(scoville)
        if first >= K:
            break
        if len(scoville) == 0:
            return -1
        second = hq.heappop(scoville)
        hq.heappush(scoville, first + second*2)
        answer += 1  

    return answer

import heapq
def solution(scoville, K):
    h=[]
    for i in scoville:
        heapq.heappush(h, i)
    
    cnt=0
    while h[0]<K:
        heapq.heappush(h, heapq.heappop(h)+heapq.heappop(h)*2)
        cnt+=1
        
        if len(h) == 1 and h[0] < K:
            return -1
    return cnt

 

 

알게된 점

 

heapify()

기존 리스트를 heap으로 변환하려면 heapq 모듈의 heapify() 함수 이용

 

heapify() 함수를 사용할 때 주의할 점은 새로운 리스트를 반환하는 것이 아니라 인자로 넘긴 리스트에 직접 변경한다는 것. 따라서 원본 리스트의 형태를 보존해야되는 경우에는 반드시 해당 리스트를 복제한 후에 인자로 넘겨야 함.

 

 

 

참조

파이썬의 heapq 모듈로 힙 자료구조 사용하기 | Engineering Blog by Dale Seo

파이썬의 heapq 모듈로 힙 자료구조 사용하기