[알고리즘 일기] 68. 더 맵게 / 힙 자료구조

문제 68. (2021-07-07) 

 

 

코딩테스트 연습 - 더 맵게

Programmers. 더 맵게

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.

Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

* scoville의 길이는 2 이상 1,000,000 이하입니다.

* K는 0 이상 1,000,000,000 이하입니다.

* scoville의 원소는 각각 0 이상 1,000,000 이하입니다.

* 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

❧ 입출력 예

---

❧ 정답

import heapq

def solution(scoville, K):
    num = 0
    heapq.heapify(scoville)
    while scoville[0] < K:
        if len(scoville) == 1:
            return -1
        heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville)*2)
        num += 1

    return num

1️⃣ 반복문 돌때 마다 sort 함수 사용 -> 런타임 에러 발생

2️⃣ 시간 단축을 위해 _시간 복잡도 O(lg n)_의 힙 자료구조 사용

---

힙(Heap)

: 완전 이진 트리를 기본으로 하는 자료 구조

* 최댓값, 또는 최솟값 탐색 연산을 빠르게 수행할 수 있다.

(기본 max, min 함수의 경우 시간 복잡도 O(n) 소요, heap 의 경우 시간 복잡도 O(lg n) 소요)

 

•최소 힙(Min Heap) : 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙

•최대 힙(Max Heap) : 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

heapq 모듈을 import 하여 파이썬에서 힙을 구현할 수 있다.

•heapq.heappush(heap, item)

•heapq.heappop(heap)

•heapq.heapify(x) : 기존에 리스트가 있을 경우, heap으로 변환

└ 시간복잡도 O(n) 소요

 

💡 기본적인 힙 구조는 최소 힙이므로, 최대 힙을 구성하려면 튜플구조로 요소를 추가하여 응용하면 된다!

heap_items = [1, 2, 3, 4, 5]
heap = []

for i in heap_items:
  heapq.heappush(heap, (-heap_items, heap_items))

→ 원소 값을 가져올 땐, heap[1]을 사용한다.