[프로그래머스/Python] 힙 - 디스크 컨트롤러

👩🏻‍🏫 풀이

import heapq
def solution(jobs):
   answer,  now, i = 0, 0, 0
   start = -1
   heap = []
   while i < len(jobs):
       for j in jobs:
           if start < j[0] <= now:
               heapq.heappush(heap,[j[1],j[0]])
       if len(heap) > 0:
           cur = heapq.heappop(heap)
           start = now
           now += cur[0]
           answer += now - cur[1]
           i += 1
       else:
           now += 1
           
   return answer // len(jobs)

• 현재 시점에서 처리할 수 있는 작업들을 힙에 넣고, 하나를 뽑아 현재 시점과 총 대기시간을 구해주는 것을 모든 작업을 처리할 때까지 반복한다.

• 힙에 push를 할 때는 작업의 소요 시간 기준으로 최소힙이 만들어져야 하기 때문에 jobs의 요소를 그대로 넣지 않고 [작업의 소요 시간, 작업이 요청되는 시점]으로 요소의 앞 뒤를 바꿔서 넣어준다.

• 현재 시점에서 처리할 수 있는 작업인지를 판별하는 조건은 작업의 요청 시간이 바로 이전에 완료한 작업의 시작 시간(start)보다 크고 현재 시점(now)보다 작거나 같아야 한다.

• 만약 현재 처리할 수 있는 작업이 없다면, 남아 있는 작업들의 요청 시간이 아직 오지 않은 것이기 때문에 현재 시점(now)을 하나 올려준다.