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

Heap

최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조입니다.

부모노드와 자식 노드 사이에 대소 관계가 성립하며(자식 노드간에는 대소관계 없음) 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙을 최대 힙, 부모 노드의 키 값이 자식 노드의 키 값보다 작은 힙을 '최소 힙'이라고 합니다.

 

위 이미지는 최대 힙을 나타냅니다.

 

 

 

파이썬 heapq 모듈

인덱스 k번째 노드는 그 자식 노드 2K+1과 2K+2  보다 항상 작은 최소 힙의 형태로 정렬되게 합니다.

 

heapq.heappush(list, item) : item을 list에 추가

heapq.heappop(list) : list에서 가장 작은 원소를 pop, 리턴 비어있는 경우 IndexError호출됨

heapq.heapify(list) : list를 바로 heap으로 변환(O(N))

 

최대 힙

파이썬 heapq 모듈은 최소 힙으로 구현되어 있으므로 최대 힙 구현을 위해서는

힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주고 실제 원소 값은 튜플의 두번째 인덱스에 접근합니다.

 

 

프로그래머스 - 더 맵게

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)

    while len(scoville) >=2 :

        if scoville[0] >= K :
            return answer
        answer += 1
        min_ = heapq.heappop(scoville)
        min_2 = heapq.heappop(scoville)
        heapq.heappush(scoville, min_ + min_2*2)

    if scoville[0] >=K :
        return answer
    else:
        return -1