TIL#143 프로그래머스 2단계 - 더 맵게

해당 문제는 힙 자료구조를 알아야 풀 수 있다.

힙(heap)

완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러개의 값들 중에서 최대값이나 최소값을 빠르게 찾아낼 수 있다. 이진탐색트리에서는 중복된 값을 허용하지 않으나 힙 트리에서는 중복된 값을 허용한다.

• 최대 힙 (max heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙 (min heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
    
• 부모 노드와 자식 노드의 관계
  • 왼쪽 자식 노드의 인덱스 = (부모 노드의 인덱스) * 2
  • 오른쪽 자식 노드의 인덱스 = (부모 노드의 인덱스) * 2 + 1
  • 부모 노드의 인덱스 = (자식 노드의 인덱스) / 2

---

파이썬에는 heapq라는 이진 트리 기반의 최소힙 자료구조를 제공하는 내장 모듈이 있다.
import heapq

• 힙에 원소 추가
  heapq.heappush(원소를 추가할 리스트, 추가할 원소)
• 힙에서 원소 삭제
  가장 작은 원소를 삭제 후에 그 값을 리턴한다.
  heapq.heappop(대상 리스트)
• 최소값 삭제하지 않고 얻기
  최소힙에서 인덱스 0번이 최소값이기 때문에 리스트의 첫번째 원소에 접근하는 것과 같다.
  대상리스트[0]
• 기존의 리스트를 힙으로 변환
  heapq.heapify(대상리스트)

---

# 예제 풀이 

import heapq


def solution(scoville, K):
    # 리스트를 최소힙으로 변환 
    heapq.heapify(scoville)
    count = 0
    while True:
        # 최소힙의 원소가 1개이고 남은 1개의 원소도 K보다 작으면 모든 원소가 K 미만이기 때문에 -1 반환
        if len(scoville) == 1 and scoville[0] < K:
            return -1
        # 인덱스 0번이 최소값이기 때문에 최소값이 K보다 작으면 최소값과 그다음 최소값을 리스트에서 제거한 후 주어진 계산식에 맞게 계산하여 리스트에 추가
        elif scoville[0] < K:
            first_min = heapq.heappop(scoville)
            second_min = heapq.heappop(scoville)
            heapq.heappush(scoville, first_min + second_min * 2)
            count += 1
        else:
            break
    return count