Programmers - 디스크 컨트롤러

문제 링크

python에서 heap은 deque와 사용법이 다른 것 같다.

deque 사용법

from collections import deque

q = deque([1, 2, 3, 4])
q.appendleft(0)
print(q)  # deque([0,1,2,3,4])
q.popleft()
print(q)  # deque([1,2,3,4])

heapq 사용법

import heapq

li = [4, 3, 2, 1]
heapq.heapify(li)
print(li)  # [1,3,2,4]
heapq.heappush(li, 0)
print(li)  # [0,1,2,4,3]
heapq.heappop(li)
print(li)  # [1,3,2,4]

• (참고) heapq는 min heap이기 때문에 max heap으로 쓰고 싶은 경우 값에 -를 붙여주는 트릭을 사용해야 한다.

문제 풀이 코드

from collections import deque
import heapq


def solution(jobs):

    heap = []
    job_queue = deque(sorted(jobs))

    time = 0
    answer = 0

    # current = [전체 작업시간,요청받은 시간, 남은 작업 시간]
    current = None

    while not (len(job_queue) == 0 and len(heap) == 0 and current == None):
        # job_queue에서 heap으로 작업 할당
        while True:
            if len(job_queue) == 0:
                break

            [req_time, work_time] = job_queue[0]
            if req_time == time:
                heapq.heappush(heap, (work_time, req_time))
                job_queue.popleft()
            else:
                break

        # 작업이 있으면 작업
        if current != None:
            current[2] -= 1
            if current[2] == 0:
                # print("작업 완료", time, current)
                answer += (time - current[1])
                current = None

        # 현재 작업이 없고, 대기작업이 있으면 작업
        if current == None and len(heap) > 0:
            (current_work_time, current_req_time) = heapq.heappop(heap)
            current = [current_work_time, current_req_time, current_work_time]
            # print("작업 할당", time, current)

        time += 1

    return answer//len(jobs)