힙 (Heap)

힙은 특정한 규칙을 가지는 트리로, 힙을 이용해서 우선순위 큐를 구현할 수 있다. 많은 언어에서 이미 구현된 우선순위 큐 라이브러리를 제공하며, 이를 활용하면 효율적으로 문제를 풀 수 있다. python의 경우에는 heapq라는 라이브러리를 용도에 맞게 사용하면 된다. 힙 알고리즘에 대한 예를 정리해 보았다.

1. 더 맵게

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 작성한다.

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

예시 1

def solution(scoville, K):
    answer = 0
    for i in range(len(scoville) - 1):
        scoville.sort()
        new = scoville.pop(0) + 2 * scoville.pop(0)
        scoville.insert(0, new)
        answer += 1
        if min(scoville[:2]) >= K: # 이걸 scoville[0] 하면 틀림. 새로 만든 값이 최소가 아닐 수도 있기 때문
            return answer
    return -1

오름차순 정렬하면 scoville의 0,1번째 값이 가장 맵지 않은 음식과 두 번째로 맵지 않은 음식이므로, 그 두 개를 빼고 섞은 음식을 넣어 계속해서 비교함
섞은 음식이 추가된 후에 섞은 음식이 스코빌 지수가 가장 낮은 음식이 아닐 수도 있으므로, 그 다음 값과의 최소값을 K와 비교함
시간 초과. .sort는 시간 복잡도가 n * log n으로 매우 크기 때문

예시 2

import heapq as hq

def solution(scoville, K):
    answer = 0
    hq.heapify(scoville)
    for i in range(len(scoville) - 1):
        new = hq.heappop(scoville) + 2 * hq.heappop(scoville)
        hq.heappush(scoville, new)
        answer += 1
        if scoville[0] >= K:
            return answer
    return -1

heap 라이브러리인 heapq 사용
.heapify는 시간 복잡도가 log n으로 .sort보다 작으며, 기본적으로 최소값이 맨 앞에 정렬되는 자료구조
따라서 맨 앞의 값만 지속적으로 비교하면 됨

출처