[프로그래머스 | Python] 더 맵게

프로그래머스_더 맵게

길이가 1e6 이상이고, 오름차순으로 앞에서 2개의 숫자를 꺼내서 사용해야 하는 점을 보고 heapq가 생각났다
deque보다 heapq가 더 빨리 작동하고, 최소큐이기 때문에 pop을 하면 자동적으로 최솟값을 내보낸다

import heapq
def solution(scoville, K):
    answer = 0
    heap = []
    for s in scoville:
        heapq.heappush(heap, s)
    
    flag = False
    while heap:
        first = heapq.heappop(heap)
        if first >= K:
            flag = True
            break       
        
        if heap:
            second = heapq.heappop(heap)
            new = first + second*2
            heapq.heappush(heap, new)
            answer += 1
        
    if flag:
        return answer
    else:
        return -1

문제를 통과하기는 했는데 효율성 테스트에서 최악의 경우 1794.19ms가 나왔다. 코드가 좀 지저분한 것 같기도해서, 다른 분들이 코드를 더 살펴보았다.

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville) #heapify : 기존list를 heapq로 만들어주는 함수
    
    while scoville[0]<K:
        try:
            new = heapq.heappop(scoville) + heapq.heappop(scoville)*2
            heapq.heappush(scoville, new)
            answer += 1
        except IndexError:
            return -1
    
    return answer

여러 코드를 보면서 heapq.heapify를 알게 되었다
이 함수를 쓰면 따로 리스트를 선언하고 heapq로 만들어줄 필요가 없이, 기존에 있던 리스트를 바로 heapq로 사용할 수 있다

위의 내 풀이에서 heapq가 비어서 발생하는 런타임에러(인덱스에러)를 try, except로 깔끔하게 해결한 부분도 좋았다

효율성 검사에서 최악의 경우가 2141.05ms가 나오기는 했지만, 다른 분의 코드가 더 깔끔하고 좋은 것 같다