programmers_고득점키트(힙정렬)

목차

1. 더 맵게
2. 라면공장
3. 디스크 컨트롤러
4. 이중우선순위큐

1. 더 맵게

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while True:
        min1 = heapq.heappop(scoville)
        if min1 >= K:
            break
        elif len(scoville) == 0:
            answer = -1
            break
        min2 = heapq.heappop(scoville)
        new_scoville = min1 + 2*min2
        heapq.heappush(scoville, new_scoville)
        answer += 1
    return answer
print(solution([1, 2, 3, 9, 10, 12], 7))

2. 라면공장

import heapq
def solution(stock, dates, supplies, k):
    answer = 0
    heap = []
    idx = 0  # lastAddedIdx
    while stock < k:
        while idx < len(dates) and dates[idx] <= stock:
            heapq.heappush(
                heap, (-supplies[idx], supplies[idx]))
            idx += 1
        stock += heapq.heappop(heap)[-1]
        answer += 1

    return answer

3. 디스크 컨트롤러

• 최근에 푼 문제 중 가장 어려웠다.

import heapq


def solution(jobs):
    last = -1
    now = 0
    answer = 0
    wait = []
    n = len(jobs)
    count = 0
    while(count < n):
        for job in jobs:
            if last < job[0] <= now:  # 처음에는 0이 들어와야 하니까. -1과 0
                answer += (now-job[0])
                heapq.heappush(wait, job[1])
        if wait:
            answer += len(wait)*wait[0]
            last = now
            now += heapq.heappop(wait)
            count += 1
        else:
            now += 1
    return answer//n


print(solution([[0, 3], [1, 9], [2, 6]]	))

# sorted [0,1,3,5,6]

4. 이중우선순위큐

import heapq


def solution(operations):
    h = []
    for i in operations:
        a, b = i.split(" ")
        if a == "I":
            heapq.heappush(h, int(b))
        else:
            if len(h) > 0:
                if b == "1":  # 큐에서 최댓값 삭제
                    h.pop(h.index(heapq.nlargest(1, h)[0]))
                else:
                    heapq.heappop(h)
    return [0, 0] if not h else [heapq.nlargest(1, h)[0], heapq.nsmallest(1, h)[0]]


print(solution(["I 7", "I 5", "I -5", "D -1"]))

---

참고자료 [프로그래머스]https://programmers.co.kr/learn/challenges