[Python - 프로그래머스] 힙(Heap) > 더 맵게

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

프로그래머스

 

---

 

Solution

 

이 문제는 사실 효율성이 더 중요한 문제다. 주어진 테스트 케이스를 모두 통과해도 효율성 테스트에서 실패하는 경우가 많다.

문제에도 나와있지만 heap으로 풀면된다.

 

import heapq
def solution(scoville, K): 
    heapq.heapify(scoville) # list to heap
 
    cnt = 0
    while scoville[0] < K :
        cnt += 1
        try :
            m1 = heapq.heappop(scoville)
            m2 = heapq.heappop(scoville)
            heapq.heappush(scoville, m1 + (m2*2))
        except :
            return -1
    return cnt

 

처음에는 그냥 list 그대로 sort해서 풀었는데, while문 안에서 매 번 sort하는게 시간이 오래걸려 효율성테스트에서 통과하지 못한다.

파이썬은 다행이 heap이 이미 library로 있어서 가져다 쓰면되는데, 다른 언어로 한다면 직접 구현해야 한다.

 

다른 사람의 풀이에 보면 queue로도 잘 풀린다고 한다.

 

어떻게 해도 해결이 안되면 -1를 return하라는 것은  scoville = [0,1], K = 7 과 같은 case를 의미한다.