[프로그래머스] 더 맵게 / 파이썬(python)

# 문제 링크

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

코딩테스트 연습 - 더 맵게

# Soultion

처음에 스택을 이용하여 문제를 풀었더니 시간초과 문제가 발생하였다.

최대값이나 최소값을 구하는 문제에는 힙큐를 사용하면 빠르게 구현이 가능하다.

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville) #힙큐로 변환
    
    while(1):
        a = heapq.heappop(scoville)
        
        if a>=K:
            break
        if len(scoville)<=0:
            return -1
        
        b = heapq.heappop(scoville)
        heapq.heappush(scoville, a+b*2)
        answer+=1
    
    return answer

 

4. 스택을 힙큐로 변환해준다. (heapify사용)

7. 최소값을 뽑아낸다.

9. 만약 최소값이 K보다 크다면 종료

11. 힙큐에 남아있는 원소가 0보다 작다면 -1을 리턴