디스크 컨트롤러 (python)

프로그래머스 문제 디스크 컨트롤러 - LV3

https://programmers.co.kr/learn/courses/30/lessons/42627
필요에 따라 순서를 바꿔서 heap을 사용하는 문제
빈번한 최소값 도출

👀 깃헙 소스

문제설명
각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

입출력 예

jobs				return
[[0, 3], [1, 9], [2, 6]]	9

솔루션

요청이 들어온 경우(cur_time보다 request가 작거나 같은경우)와
요청이 들어온 것이 없는 경우를 나누어 푼다.
1)요청이 들어 온 것이 없을 때는 현재 시간을 request + time으로 설정해준 후 기다린 시간이 없으므로 waits에 time만 더해주면 된다.
2) 요청이 들어온 것이 있을 때는 들어온 것들 중 실행시간이 가장짧은 것을 실행 해준다. 바로 실행하므로 현재시간은 time을 더한 값이 된다. 대기시간이 있으므로 waits에 curr_time - request값을 더해준다.
3) 요청을 cand에 넣어주는 처리를 할 때는 실행시간 값을 기준으로 작은 값을 빼내야 하므로 heappush를 해줄 때 순서를 바꿔서([::-1]) 실행시간이 앞에 위치하도록 한다.

코드

# 파이썬
import heapq
from collections import deque
def solution(jobs):
    N, REQUEST = len(jobs), 0
    jobs = deque(sorted(jobs))
    jobs_done, curr_time, waits, cand = 0, 0, 0, []
    # 일을 다 마칠 때 까지
    while jobs_done < N:
        # 요청이 들어온 것이 없을 때
        if not cand:
            request, time = jobs.popleft()
            curr_time = request + time
            waits += time
        # 요청이 들어온 것이 있을 때
        else:
            time, request = heapq.heappop(cand)
            curr_time += time
            waits += curr_time - request

        jobs_done += 1
            
        while jobs and jobs[0][REQUEST] <= curr_time:
            heapq.heappush(cand, jobs.popleft()[::-1])
            
    return waits // N

팁
힙은 첫번째 요소를 기준으로 최소값을 뽑아내므로 필요에따라 순서를 바꿔서 사용하면 좋다.