[프로그래머스] Lv.2 더 맵게 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42626
• heapq 모듈 사용
• heapq는 이진 트리 기반의 최소 힙 자료구조를 제공
• 최소 힙으로 항상 오름차순 정렬되어 있다. 정렬된 상태를 유지해야 할 때 계속 정렬할 필요가 없어 속도가 빠르다.
• heapity() : 리스트를 heap으로 변환, O(N)
• heappush() : heap에 원소 추가, O(log(n))
• heappop() : heap에서 가장 작은(0번 인덱스) 원소 삭제, O(log(n))

 

from heapq import heapify, heappush, heappop

def solution(scoville, K):
    answer = 0

    heapify(scoville) # 리스트를 힙으로 변환

    while scoville[0] < K:
        if len(scoville) == 1 and scoville[0] < K: return -1

        x = heappop(scoville)	# 가장 작은 원소 꺼냄
        y = heappop(scoville)	# 두 번째 작은 원소 꺼냄
        new = x + y * 2			# 새로운 값 생성

        heappush(scoville, new)	# 새로운 값을 heap에 추가
        answer += 1
    
    return answer