[프로그래머스] 고득점Kit (3) - 힙 (파이썬)

1. 더 맵게 (Lv. 2)

# 더 맵게
import heapq


def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville[0] < K:
        if len(scoville) >= 2:
            new = heapq.heappop(scoville) + (heapq.heappop(scoville)*2)
            heapq.heappush(scoville, new)
            answer += 1
        else:
            answer = -1
            break
    return answer

 

scoville리스트를 heapq로 만들어준다. (heapq.hepify)

가장 작은 값(scoville[0])이 K보다 작으면 두 재료를 섞어서 새로운 스코빌 지수를 가진 재료를 scoville에 넣어 준다.

재료를 섞을 때마다 answer += 1

남은 재료가 2개보다 적으면 answer = -1

---

2. 디스크 컨트롤러 (Lv. 3)

# 디스크 컨트롤러
import heapq


def solution(jobs):
    leng = len(jobs)
    jobs.sort(reverse=True)
    heap = []
    now, answer = 0, 0
    while heap or jobs:
        if heap:
            temp = heapq.heappop(heap)
            answer += now + temp[0] - temp[1]
            now += temp[0]
        for i in range(len(jobs)-1, -1, -1):
            start, dur = jobs[i]
            if now >= start:
                s, dur = jobs.pop()
                heapq.heappush(heap, [dur, s])
            else:
                if not heap:
                    now += 1
                break
    answer //= leng
    return answer

 

jobs를 내림차순으로 정렬을 해준다. (pop을 이용하기 위해서)

heap이 존재하거나, jobs가 존재한다면 무한반복

    - heap이 있으면 가장 적게 걸리는 요소를 실행 (answer += 현재 시점(now) + 걸리는 시간 + 시작시간) (now += 걸리는 시간)

    - jobs를 pop해가면서 현재 시점에서 실행 가능한 모든 프로그램을 heap에 push [걸리는 시간, 시작시간]

    - heap도 비어있고, 현재 실행 가능한 프로그램이 없다면 현재 시점(now) += 1

answer를 총 길이만큼 나눈 몫 return

---

3. 이중우선순위큐 (Lv. 3)

# 이중 우선순위 큐
import heapq


def solution(operations):
    max_heap = []
    min_heap = []
    visited = [False] * len(operations)
    for i, oper in enumerate(operations):
        order, num = oper.split()
        num = int(num)
        # push
        if order == 'I':
            heapq.heappush(min_heap, [num, i])
            heapq.heappush(max_heap, [-num, i])
        # pop
        if order == 'D':
            if num == 1:
                if max_heap:
                    is_ok(max_heap, visited)
            else:
                if min_heap:
                    is_ok(min_heap, visited)

    answer = [0, 0]
    if min_heap:
        number, index = heapq.heappop(min_heap)
        while min_heap and visited[index]:
            number, index = heapq.heappop(min_heap)
        if not visited[index]:
            answer[0] = number
            answer[1] = number
    if max_heap:
        number, index = heapq.heappop(max_heap)
        while max_heap and visited[index]:
            number, index = heapq.heappop(max_heap)
        if not visited[index]:
            answer[0] = -number
            if answer[1] == 0:
                answer[1] = -number

    return answer


def is_ok(heap, visited):
    number, index = heapq.heappop(heap)
    while heap and visited[index]:
        number, index = heapq.heappop(heap)
    visited[index] = True

 

최소 힙과 최대 힙 두 가지를 정의

I 일 때, 두 가지 힙 모두에 push

D 이고 1이면, max_heap에서 존재하는 값이 나올 때까지 pop, visited(pop여부) = True

D 이고 -1이면, min_heap에서 존재하는 값이 나올 때까지 pop, visited(pop여부) = True

answer 초기값 = [0, 0]

max_heap에서 존재하는 값이 나올 때까지 pop, 이후 visited가 False라면 answer[0] 업데이트

min_heap에서 존재하는 값이 나올 때까지 pop, 이후 visited가 False라면 answer[1] 업데이트