[프로그래머스 | 파이썬] 더 맵게(힙(Heap)/ level 2)

문제

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

프로그래머스

 

 

🐍파이썬

import heapq
def solution(scoville, K):
    cnt = 0
    heapq.heapify(scoville)	#기존 리스트를 heap으로 변환
    while scoville[0] < K:	#heap의 최솟값이 K보다 작은 경우
        heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville) * 2)	#힙에서 가장 작은 원소 + 그다음 작은 원소 * 2 진행 후 heap에 push
        cnt += 1	#섞은 횟수 카운트
        if scoville[0] < K and len(scoville) == 1:	#heap의 최솟값이 K보다 작으면서 길이가 1이면 == 스코빌지수 K이상 달성X, 섞기 불가
            return -1
    return cnt

💡 heapq 모듈

데이터를 정렬된 상태로 저장하기 위해서 사용하는 파이썬 내장모듈, 기본적으로 최소힙

- heapify(): 기존 리스트를 힙으로 변환

- heappush(힙 리스트, 힙에 push할 원소): 힙에 원소를 추가

- heappop(힙 리스트): 힙에서 가장 작은 원소 삭제

(참고: https://www.daleseo.com/python-heapq/)

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

 

 

다른 풀이 방법

from heapq import heapify, heappush, heappop
def solution(scoville, K):
    heapify(scoville)
    for i in range(1000000):
        try:
            heappush(scoville, heappop(scoville)+(heappop(scoville)*2))
            if scoville[0] >= K: return i+1
        except:
            return -1

---

import heapq
def solution(scoville, K):
    heapq.heapify(scoville)
    size, cnt = len(scoville) - 1, 0
    f = heapq.heappop(scoville)
    while size > 0:
        s = heapq.heappop(scoville)
        f = heapq.heappushpop(scoville, f + s + s)
        if f >= K:
            return cnt + 1
        cnt += 1
        size -= 1
    return -1