[코딩테스트 고득점 Kit/Python] 힙(Heap)

힙(heap)이란?

 

• 최댓값과 최솟값을빠르게 찾기 위해 고안된 자료구조
• 원소들이 항상 정렬된 상태로 추가되고 삭제
• 시간 복잡도 O(N)

힙 함수 활용하기

 

• heapq.heappush(heap, item)
  • heap에 item을 추가
• heapq.heappop(heap) 
  • heap에서 가장 작은 원소를 pop
  • 힙이 비어 있는 경우, IndexError가 호출됨
• heapq.heapify(x) 
  • 기존 리스트를 heap으로 변환

---

문제 풀이

 

Q . 더 맵게 

import heapq


def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    # 가장 작은 값이 K보다 클 때는 섞을 필요 X
    if scoville[0] >= K:
        return answer
    
    while scoville[0] < K:
        if len(scoville) == 1:	# 원소가 1개라 모든 음식의 스코빌 지수를 K 이상으로 못 만듦
            return -1
        heapq.heappush(scoville, (heapq.heappop(scoville) + heapq.heappop(scoville) * 2))
        answer += 1
    return answer

Q . 디스크 컨트롤러

import heapq


def solution(jobs):
    heap = []
    answer, now, i = 0, 0, 0   
    s = -1
    
    while i < len(jobs):
        for j in jobs:
            if s < j[0] <= now:
            	# 작업시간 짧은 순서대로 처리해야 총 작업시간 최소됨
                heapq.heappush(heap, (j[1], j[0]))
        
        if heap:
            current = heapq.heappop(heap)
            s = now	# 작업 종료시간
            now += current[0]	# 현재 작업까지의 작업시간 누적값
            answer += now - current[1]	# 요청에서 종료까지 걸린 시간, current[1] = 요청 들어온 시간
            i += 1
        else:
            now += 1
        
    return answer // i

Q . 이중우선순위큐 

import heapq


def solution(operations):
    heap = []
    max_heap = []

    for i in operations:
        current = i.split()
        if current[0] == 'I':
            data = int(current[1])
            heapq.heappush(heap, data)
            # 최대 힙 구현 위해 [우선순위, 실제값] 형태로 저장
            heapq.heappush(max_heap, (data * -1, data))
        else:
            # heap 비어있으면 실행할 코드가 없는 것으로 간주하여 다음 행동을 계속해서 진행
            if len(heap) == 0:
                pass
            # 최댓값 삭제
            elif current[1] == '1':
                max_value = heapq.heappop(max_heap)[1]
                heap.remove(max_value)
            # 최솟값 삭제
            elif current[1] == '-1':
                min_value = heapq.heappop(heap)
                max_heap.remove((min_value * -1, min_value))

    if heap:
        return [heapq.heappop(max_heap)[1], heapq.heappop(heap)]
    else:
        return [0, 0]