[프로그래머스] 고득점 Kit - 힙

[내 풀이]
# 최솟값이 계속 변화하고, 그것을 기준으로 알고리즘이 돌아가야함 => heapq 사용
# 런타임 에러: 아예 불가능한 경우 return -1 를 고려하지 않음

import heapq as hq
def solution(scoville, K):
    scoville.sort()
    cnt = 0
    while len(scoville) >= 2 and scoville[0] < K:
        a, b = hq.heappop(scoville), hq.heappop(scoville)
        hq.heappush(scoville, a + 2 * b)
        cnt += 1
    return cnt if scoville[0] >= K else -1

디큐는

https://yunaaaas.tistory.com/36

[내 풀이]
# 큐로 한쪽에서만 꺼낼 것이라면 굳이 deque()로 변환하지않고 정렬을 reverse=True로 한 후, pop() 을 이용하자
# 힙에는 '조건 맞는 것들 중' 정렬이 필요한 값들을 넣는다
import heapq as hq
def solution(jobs):
    jobsSorted = deque(sorted([[sT, yT] for yT, sT in jobs], key=lambda x:(x[1],x[0])))
    cT = 0
    tT = 0
    Q = []
    hq.heappush(Q, jobsSorted.popleft())
    while Q:
        sT, yT = hq.heappop(Q)
        cT = max(yT+sT, cT+sT) # 작업 완료 시간
        tT += cT - yT
        while jobsSorted and jobsSorted[0][1] <= cT:
            hq.heappush(Q, jobsSorted.popleft())
        if jobsSorted and not Q:
            hq.heappush(Q, jobsSorted.popleft())
    return tT//len(jobs)

[참고 풀이]
import heapq
from collections import deque

def solution(jobs):
    tasks = deque(sorted([(x[1], x[0]) for x in jobs], key=lambda x: (x[1], x[0])))
    q = []
    heapq.heappush(q, tasks.popleft())
    current_time, total_response_time = 0, 0
    while len(q) > 0:
        dur, arr = heapq.heappop(q)
        current_time = max(current_time + dur, arr + dur)
        total_response_time += current_time - arr
        while len(tasks) > 0 and tasks[0][1] <= current_time:
            heapq.heappush(q, tasks.popleft())
        if len(tasks) > 0 and len(q) == 0:
            heapq.heappush(q, tasks.popleft())
    return total_response_time // len(jobs)

(우선 순위, 값) 으로 지정 가능

https://www.daleseo.com/python-heapq/

 

# 내 풀이
#무의식적으로 힙이 정렬된 리스트랑 같다고 생각했다.
#힙은 최소값만 보장하지, 나머지 값들은 오름차순이 아니라는 것을 주의해야한다.
#파이썬에서는 평범한 리스트에 heapq 함수를 사용하는 것일 뿐이다. 따라서 heappush를 한다고 힙이 되는 것은 아니다.
#일반 리스트를 힙 구조로 바꾸고 싶다면 O(n)이 걸리고 .heapify() 함수를 이용하면 된다. remove후에 꼭 다시 heapify()해주어야 한다. 
import heapq as hq
def solution(operations):
    operations = [x.split() for x in operations]
    answer = []
    for op, x in operations:
        if op == "I":
            hq.heappush(answer, int(x))
        elif op == "D":
            if answer:
                if x=="-1":
                    hq.heappop(answer)
                else:
                    answer.remove(max(answer))
                    hq.heapify(answer) #꼭 heapify 다시 해주어야 한다.
    return [max(answer), answer[0]] if answer else [0, 0]