[Programmers, Lv.2] 코딩테스트 고득점 Kit - 힙(Heap) (1), 더 맵게 (Python)

😳 힙(Heap) 기초 개념 간단하게 살펴보기

---

• 힙(Heap)이란? : "완전 이진트리"라는 형태적 속성과, "모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 같다"는 힙 속성을 모두 만족시키는 자료구조이다. (즉, 힙을 이해하기 위해서는 트리를 먼저 알아야만 한다!)
  
• 그렇다면, 트리(Tree)란? : 데이터의 상-하 관계를 계층적으로 나타내는 자료구조이다. (말 그대로, 트리 모양을 생각하면 되겠다.)-> 맨 위에 있는 노드를 Root 노드, 트리 연결의 가장 마지막 노드를 Leaf 노드라고 부른다.-> 데이터의 상-하 관계를 부모 노드-자식 노드 관계라고 부르며, 같은 깊이에 있는 노드들끼리는 형제 노드라고 부른다.
  
  
• 트리의 종류는 어떤 것들이 있을까?
  • 이진트리 (Binary Tree) : 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리
  • 정 이진 트리 (Full Binary Tree) : 모든 노드가 2개 또는 0개의 자식을 갖는 이진트리
  • 완전 이진트리 (Complete Binary Tree) : 마지막 레벨 직전의 트리까지는 모든 노드들이 다 채워져 있어야 하며, 마지막 레벨에서는 노드들이 다 채워져있지 않더라도 왼쪽부터 오른쪽 방향 순으로 노드들이 채워져 있어야 한다. -> 동적 배열로 구현이 가능하다.
  • 포화 이진 트리 (Perfect Binary Tree) : 모든 레벨들이 빠짐없이 노드들로 가득 채워져 있는 이진 트리

트리의 구조 살펴보기 (출처: 코드잇 "알고리즘과 자료구조" 강의)

 

힙과 큐를 편하게 사용할 수 있도록 파이썬에서는 heapq라는 라이브러리를 지원한다.
아래 코드를 보며 간략하게 오늘 사용하게 될 heapq 라이브러리의 모듈 사용법들을 읽고 넘어가 보자!

# heapq 라이브러리 호출
import heapq as hp

# 사용 가능한 heapq 라이브러리 모듈
hp.heapify(x)			# 리스트 x를 힙으로 반환한다.

hp.heappush(heap, item)		# item 값을 heap으로 push한다.
hp.heappop(heap)		# heap에서 가장 작은 값을 pop한다(=빼낸다).
hp.heappushpop(heap, item)	# heap에 item을 push한 후, heap에서 가장 작은 값을 pop한다. (개별 호출하는 것보다 더 효율적)
hp.heapreplace(heap, item)	# heap에서 가장 작은 값을 pop한 후, 새로운 item을 push한다. (개별 호출하는 것보다 더 효율적)

# 힙에서 최소값을 삭제하지 않고, 얻으려고 할 때 사용 가능한 방법
# 주의! 두번째로 작은 원소를 얻으려면 바로 heap[1]으로 접근하면 안된다.
# 힙은 heappop() 함수를 호출하여 원소를 삭제할 때마다 이진 트리의 재배치를 통해 매번 새로운 최소값을 인덱스 0에 위치시키기 때문! 
# 따라서, 반드시 heappop()을 통해 가장 작은 원소를 삭제 후에 heap[0]를 통해 새로운 최소값에 접근해야 한다.
heap[0]

 

📎 프로그래머스 문제 링크

---

프로그래머스

 

🤔 문제설명, 제한사항, 입출력 예

---

Leo가 가진 음식의 스코빌 지수(음식의 매운 정도를 숫자로 표현한 수치)를 담은 배열 scoville과 원하는 스코빌 지수를 K가 주어질 때,
모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 구하라는 문제이다.

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을
"가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)"의 방법으로 섞어 새로운 음식을 만든다고 한다.

모든 음식의 스코빌 지수가 K 이상이 될 때까지 계속 반복하여 섞을 것이며,
만약 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 반환시키면 된다고 한다.
scoville 리스트의 길이는 2 이상, K는 0 이상의 수치를 가진다고 한다.

 

 

🤔 내가 생각한 풀이 과정 

---

위에서 배운 대로 우선 문제에서 주어진 scoville 리스트를 힙(Heap)으로 바꿔줘야 한다.

이제 힙에서 가장 작은 값을 가진 노드(scoville[0]으로 얻을 수 있음)를 K와 비교해 줄 것이다.
가장 작은 값을 가진 노드가 K보다 작을 경우, 스코빌 지수가 낮은 두 노드를 pop 해서 주어진 방법으로 변환해 힙에 추가해줘야 한다.
이때 주의할 점은 heap에서 가장 작은 값을 뺄 때, 인덱싱 형태로 제거하게 되면 그다음 값이 최솟값이 아닐 수도 있다는 점이다!
(이와 관련된 내용은 위 heapq 라이브러리의 모듈들을 소개하는 코드에서 주석으로 작성했으니 확인해 보도록 하자.)

이 반복 안에서 반드시 빼먹으면 안 되는 부분 하나가 -1이 반환된다는 조건이다.
전체 heap의 길이가 2이고, 이 두 노드끼리 음식을 섞어도 K가 되지 않는다면 더 이상 "모든 음식의 스코빌 지수를 K 이상으로 만들 수 없다"라고 판단할 수 있으니 이때는 -1을 반환하도록 한다.

*풀이 과정으로 생각했을 때는 쉽게 해결할 수 있을 것 같은 문제였는데, 사소한 차이로 여러 테스트 케이스에서 에러가 발생할 수 있는 문제였다. -> 큐를 사용할 때의 주의사항을 잘 생각하며 코드로 구현해 보자.

문제 풀이의 정확성을 위해 아래 두 테스트 케이스를 추가해 풀어보길 권장한다.

추가 테스트 케이스 1 : scoville = [1, 1, 2, 6], K = 24, Return = -1 -> 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우
추가 테스트 케이스 2 : scoville = [1, 1], K = 3, Return = 1 -> 한 번에 모든 음식의 스코빌 지수를 K 이상으로 만들 수 있는 경우

 

🧑🏻‍💻 코드로 확인하기

---

import heapq as hp

def solution(scoville, K):
    hp.heapify(scoville)    # scoville 리스트를 힙 자료형으로 만들기
    
    count = 0
    while scoville[0] < K : 
        count += 1
        
        min_one = hp.heappop(scoville)  
        min_two = hp.heappop(scoville)  
        hp.heappush(scoville, min_one + min_two*2)
        
        # 모든 스코빌을 K 이상으로 만들 수 없는 경우
        if (len(scoville) == 2) and (scoville[0] + scoville[1]*2) < K: 
            return -1  
        
    return count