[Python] 힙(Heap) : 프로그래머스 LV.2 더 맵게

프로그래머스

문제 :

문제 설명

매운 것을 좋아하는 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 합니다.

입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

입출력 예 설명

• 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
  새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
  가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
• 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
  새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
  가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

---

풀이과정:

먼저 문제의 풀이의 앞서, Heap이 무엇인지 알아보았다. 

힙이란?
- 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 만들어진 완전 이진트리를 기본으로 한 자료구조이다.

힙에는 두 가지 종류가 있다.
- 최소 힙(Min Heap) : 제일 위 루트 (분모 노드)에 가장 작은 값이 오도록 하는 트리구조
- 최대 힙(Max Heap) : 제일 위 루트(분모 노드)에 가장 큰 값이 오도록 하는 트리구조

파이썬에서는 힙 자료구조를 생성해 주는 heapq 라이브러리를 제공하고, 사실 형태는 일반적인 배열과 동일해 보인다.
하지만 heappush와 heappop을 이용해 배열의 값 순서를 힙 알고리즘 규칙대로 자동으로 정렬하여 배열을 만들어준다.
또한, 완성되어 있는 배열을 heapify함수를 이용해서 힙 자료구조로 변형할 수 있다.

이렇듯이, 파이썬의 heapq라이브러리를 사용하면 아주 편하게 heap 자료구조를 사용할 수 있다.

---

문제 이해하기:
더 맵게라는 문제를 이해해 보자. 스코빌이라는 매운 수치값을 가지는 배열이 주어졌을 때, 거기서 가장 안 매운 값과 두 번째로 매운 값을 찾아 주어진 공식을 이용해 계산한 후 그 값을 이용해 조건에 충족될 때까지 반복하는 문제이다. 여기서 힙 자료구조를 이용하면 매우 편리하다. 힙 자료구조는 작은 값부터 오도록 하는 완전 이진트리 자료구조이기 때문에 배열의 안의 값에서 문제가 제시한 값들을 빠르게 찾을 수 있다.

여기까지 이해한 후 문제를 푸는 것에 큰 어려움이 없었다. heapq를 이용하여 주어진 입력값을 힙 자료구조로 변경해 주는 heapify 함수를 사용해 주고, heappop함수를 이용해 첫 번째, 두 번째 값을 꺼내준 뒤 공식을 이용해 계산한 값을 배열에 다시 넣어주면 자동으로 힙 자료구조 규칙에 맞게 만들어주기 때문에 위의 과정을 반복하면서 주어진 k값 이상이 되는 순간 반복을 마치고 카운트 한 값을 출력해 주면 완료된다. 

---

결과 :

### 더 맵게

#heapq라이브러리 호출
import heapq

def solution(scoville, K):
    # 입력으로 받은 리스트를 힙 자료구조로 변환해주는 heapify함수
    heapq.heapify(scoville)
    
    count = 0
    
    while scoville[0] < K:
    # 배열 값의 개수가 2 미만이면, 새로운 스코빌을 만들 수 없으니까 -1 반환
        if len(scoville) < 2:
            return -1
        
        # 가장 맵지 않은 음식-> heapq의 heappop을 이용하면 알아서 가장 작은 노드를 빼준다.
        first_scoville = heapq.heappop(scoville)
        #두 번째로 맵지 않은 음식
        second_scoville = heapq.heappop(scoville)
        # 두 음식의 스코빌을 섞어 만든 스코빌 
        mixed_scoville = first_scoville + (second_scoville * 2)
        
        # 섞은 음식을 다시 힙에 추가해주고, 추가했으면 카운트 업해준다. 그리고 다시 반복
        heapq.heappush(scoville, mixed_scoville)
        count += 1
    
    return count