더 맵게

힙을 사용하여 푸는 문제.

문제 설명

매운 것을 좋아하는 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. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다. 새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5 가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다. 새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13 가진 음식의 스코빌 지수 = [13, 9, 10, 12]

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

문제 풀이

힙을 이용하여 가장 작은 스코빌 지수가 최소 K가 넘도록 바꾸고, 바꾸는 횟수를 반환하는 문제다. 힙이란 완전 이진 트리로 느슨하게 정렬된 상태를 유지하는 자료 구조이다. 여기서 완전 이진 트리란 각 노드가 2개의 자식을 가질 수 있고, 왼쪽에서부터 채워나가는 구조이다. 그리고 느슨하게 정렬되어있다는 것은 각 부모 노드가 자식 노드보다 작거나 크도록만 되어있다.

보통 힙을 저장하는 구조로 배열을 쓰는데, 일반적으로 0 index를 비워놓고 사용한다. 그러면 다음과 같이 부모 노드(p_idx)와 자식 노드(c_idx)의 관계를 구할 수 있다.

p_idx = int(c_idx/2)
left_c_idx = p_idx*2
right_c_idx = p_idx*2+1

이렇게 구할 수 있는 이유는 다음과 같다. 부모 노드의 오른쪽 형제 노드를 모두 지나치고 부모 노드의 왼쪽 형제의 자식 노드를 지나쳐야 도달한다. 현재 노드를 x, 현재 노드가 속해있는 레벨을 k라고 하자. 즉 \(k = \lfloor log_2(x) \rfloor\)이다. 현재 레벨에서 왼쪽에서부터의 현재 노드 위치는 \(x-2^k\)라고 하자.

그렇다면 부모 노드 왼쪽 형제들의 수는 \(x-2^k\)이고 각 노드의 자식수를 곱하면 \(2(x-2^k)\)이다.

부모 노드의 오른쪽 형제 수는 \(2^k - (x-2^k) = 2*2^k-x = 2^{k+1}-x\)이다.

즉, \(2(x-2^k)-2^{k+1}+x = x\)이다.

이제는 힙의 삽입과 삭제 기능을 보자.

삽입의 경우, 먼저 노드를 힙 마지막 부분에 넣어준다. 그리고 부모 노드와 비교하여 작거나 크다는 조건을 만족할때까지 반복해준다.

def insert(self, node):
    self.data.append(node)
    idx = len(self.data)-1
    while idx >= 0:
        p_idx = (idx-1)//2
        if self.data[p_idx] < self.data[idx]:
            self.swap(p_idx, idx) # data의 idx와 p_idx를 바꾸는 함수
            idx = p_idx
        else:
            break

삭제의 경우, 루트를 반환하고 마지막 노드를 루트 위치에 놓는다. 그리고 자식 노드와 비교해가며 작거나 크다는 조건을 만족할때까지 반복해준다. 재귀적인 호출로 반복할 수 있다.

def remove(self):
	last_idx = len(self.data)-1
    self.swap(last_idx, 0) # 루트와 마지막값을 바꾸어준다.
    min_val = self.data.pop() # 루트를 추출 후 반환
    self.heapify(0) # 힙구조로 만들어주는 재귀함수
    
    return min_val

def heapify(self, idx):
    min_idx = idx
    
    if min_idx*2+2 <=len(self.data)-1 and self.data[min_idx] > self.data[min_idx*2+2] and self.data[min_idx*2+2] < self.data[min_idx*2+1]:
        min_idx = min_idx*2+2
    elif min_idx*2+1 <=len(self.data)-1 and self.data[min_idx] > self.data[min_idx*2+1]:
        min_idx = min_idx*2+1
        
    if min_idx != idx:
        self.swap(min_idx, idx)
        self.heapify(min_idx)
    

힙을 이용하여 문제를 다음과 풀 수 있다. 루트가 K보다 클때까지 음식을 섞는 횟수를 반복하는 것이다.

def solution(scoville, K):
    answer = 0
    hp = heap()
    for each in scoville:
        hp.insert(each)

	while hp.data[1] < K and len(hp.data) > 2:
        root1 = hp.remove()
        root2 = hp.remove()
        hp.insert(root1+root2*2)
        answer +=1

	if hp.data[-1] <K:
    	return -1
	return answer

이렇게 풀면 정확도 문제는 모두 맞출 수 있지만, 효율성에서는 탈락한다. 아무래도 최적화가 되어있는 패키지를 써서 푸는 게 더 빠르다.

from heapq import heapify, heappush, heappop
def solution(scoville, K):
    answer = 0
    heapify(scoville)
    
    while scoville[0] < K and len(scoville) >1:
        root1 = heappop(scoville)
		root2 = heappop(scoville)
        heappush(scoville, root1+root2*2)
        answer +=1
   
	if scoville[-1]<K:
        return -1
    
    return answer