[프로그래머스]

문제

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

내 코드(다른 블로그 참고)

참고 블로그1

import heapq

def solution(scoville, K):
    answer = 0
    
    heap=[]
    
    for s in scoville:
        heapq.heappush(heap, s)
    
    
    while heap[0]<K:

        try:
            heapq.heappush(heap, heapq.heappop(heap)+heapq.heappop(heap)*2)
            answer+=1

        except IndexError:
            return -1
        
        
    return answer

풀이

• heapq: 힙 큐의 알고리즘을 제공
  • 최소힙만 지원
  • 최소값이 루트에 즉, 최소값이 0번 인덱스에 존재
• scoville에 있는 수들을 heapq.heqppush()를 이용해 리스트에 push

heapq.heappush(heap, item)
힙 불변성을 유지하면서, item 값을 heap으로 푸시

• heap의 0번 인덱스의 수가 가장 최소이므로, 그 수가 K보다 커질때 까지 섞은 음식의 스코빌지수를 계산한 값을 push한다

  • 가장 맵지않은 음식의 스코빌 지수는 heqpq.heppop()을 이용해 꺼내면 두번째로 맵지않은 음식의 스코빌 지수가 최소가 되므로 다시 heqpq.heppop()을 이용해 꺼낸다

heapq.heappop(heap)
힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환.
힙이 비어 있으면, IndexError가 발생.
팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용.

참고

다른 코드

참고 블로그2

from heapq import *

def solution(scoville, K):
    count = 0
    heapify(scoville)
    while scoville[0] < K and len(scoville) > 1:
        num1 = heappop(scoville)
        num2 = heappop(scoville)
        heappush(scoville, num1 + num2 * 2)
        count += 1
    return count if scoville[0] >= K else -1

• heapify로 scoville리스트를 heap으로 변환

heapq.heapify(x)
리스트 x를 선형 시간으로 제자리에서 힙으로 변환.

• try except 대신 len(scoville) > 1 조건