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

programmers.co.kr/learn/courses/30/lessons/42627

코딩테스트 연습 - 디스크 컨트롤러

해설

 

대기하는 작업들중 수행시간이 가장 작은작업을 먼저 처리해야 한다.

 

현재 작업중인 작업이 [0, 3] 라고 하자

대기 작업 [1, 9], [2, 6] 이 있다고 하자

 

저기서 대기작업들의 걸리는 시간을 생각해보면 간단하다.

 

만약 대기작업이 2개가 있다고 치자. 각각 걸리는 작업의 시간은

 

앞에오는놈 : (현재 작업중인 작업의 종료시간 - 앞에오는놈의 시작시간) + 앞에오는놈의 작업 시간

뒤에오는놈 : (현재 작업중인 작업의 종료시간 - 뒤에오는놈의 시작시간) + 앞에오는놈의 작업 시간 + 뒤에오는놈 작업의 시간

 

 

저 노란색 글씨를 제외한 나머지의 합은 순서를 바꿔도 항상 똑같다.

그러므로 앞에오는놈의 작업시간이 적어야 디스크 처리의 총 시간이 줄어든다

 

 

 

예제의 그림처럼 현재 작업중인 작업은 [0, 3] 이고 [2, 6]를 먼저 처리하고 [1, 9]을 나중에 처리한다 치자

 

[2, 6]이 앞에 올 경우

 

현재 작업중인 작업의 종료시간 : 3

본인의 시작시간 : 2

본인의 작업시간 : 6

 

( 3 - 2 ) + 6  = 7ms

 

[1, 9]이 뒤에 올 경우

 

현재 작업중인 작업의 종료시간 : 3

본인의 시작시간 : 1

앞에 오는놈의 작업시간( 여기선 [2, 6] ) : 6

본인의 작업시간 : 9

 

( 3 - 1) + 6 + 9 = 17ms

 

 

위에 예제처럼 계산이 된다.

 

 

 

 

 

 

 

 

문제풀이 코드

from collections import deque
import heapq

def solution(jobs):
    jobs.sort()
    jobq = deque(jobs)
    waitq = []
    end = 0
    length = len(jobq)
    answer = 0
    while jobq or waitq:
        while jobq and jobq[0][0] < end:
            #겹치는 작업이 있으면 작업시간이 적은걸 먼저 처리
            heapq.heappush(waitq, [jobq[0][1], jobq[0][0]])
            jobq.popleft()
            
        #대기작업이 있으면 하나만 pop하면서 end 타임 업데이트
        if waitq:
            time, start = heapq.heappop(waitq)
            end += time
            answer += end - start
        #대기 작업이 없으면 가장 앞에있는 작업 처리
        elif jobq:
            start, time = jobq[0]
            jobq.popleft()
            end = start + time
            answer += time
    answer //= length
    return answer

 

 

 

• waitq는 heap으로 사용한다. 작업시간 기준으로 정렬해야 되니 jobs에서 주어지는 인풋 순서를 바꿔주자.
• waitq push는 while문으로 잔뜩 넣어주되 waitq pop하는건 하나씩 해야된다. 그래야 end time 업데이트 한번식 해주면서 waitq를 갱신 할 수 있다.
• waitq가 비어있을경우 jobq에서 하나꺼내서 처리해준다.
• jobs는 정렬되서 주어지지 않는다. jobs 리스트를 꼭 정렬해주고 시작하도록 하자