[Algorithm - Heap] Heap에 대해서 (Programmers - 더 맵게)

heap

• 최소/ 최대 원소를 빠르게 찾을 수 있도록 만들어진 자료구조
• 완전 이진트리(complete binary tree)로 구성됨 
• 큐에 우선순위 개념을 도입한 우선순위 큐구조를 사용하며 우선순위가 높은 데이터가 먼저 나간다.
• Python heapq의연산종류와 시간복잡도
  • 힙 구성 (heapify) - O(NlogN)
  • 삽입 (heappush) - O(logN)
  • 삭제 (heappop) - O(logN)

 

 

Programmers heap 문제 - 더 맵게

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

import heapq

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

    for i in range(len(scoville)):     

        try:   
            # 가장 작은 수 POP
            scov1 = heapq.heappop(scoville)      
            if scov1 < K:
                # 두번째로 작은 수 pop
                scov2 = heapq.heappop(scoville)
                heapq.heappush(scoville , scov1 + scov2 * 2)
            else:
                answer = i
                break
        except:
            answer = -1
            break

    return answer