[프로그래머스] 디스크 컨트롤러

문제

[프로그래머스] 디스크 컨트롤러

해설

• 문제에서 요구되는 방식은, SJF(Shortest Job First)이다.
• 즉, 가장 짧은 요청 시간을 요구하는 작업부터 수행된다.

• 현재 시점에서 처리할 수 있는 job을 heappush 해준다.
• (이때, 작업의 소요 시간을 기준으로 heap이 만들어져야하기 때문에 job[1], job[0]로 주어진 job의 요소를 뒤집어서 넣어준다.)
• 현재 시점에서 처리할 수 있는 job의 기준 :
  • start(직전에 수행한 job의 시작 시간) < job의 요청 시간 <= now(현재 시간)
• 현재 시점에서 처리할 수 있는 job이 없으면, 현재 시간보다 나중 시점에 요청되는 job이 아직 오지 않은 것이기 때문에 now(현재시간)을 += 1 해준다.

코드

import heapq

def solution(jobs):
    answer = 0
    jobs.sort()
    
    start = -1 # 바로 전 작업의 시작 시간
    now = 0 # 현재 시간
    cnt = 0 # 처리된 작업의 개수
    
    hq = []
        
    while cnt < len(jobs):
        for i in jobs: # 현재 처리할 수 있는 작업들을 hq에 넣어줌
            if start < i[0] <= now:
                heapq.heappush(hq, [i[1], i[0]]) # 소요 시간 기준으로 정렬되게
        
        if len(hq)>0: # 처리할 작업이 남은 경우
            current = heapq.heappop(hq)
            start = now
            now += current[0]
            answer += now-current[1]
            cnt += 1
        else: # 처리할 작업이 없으면
            now += 1
            


        
    return answer//len(jobs)