[힙(Heap)] 디스크 컨트롤러

https://programmers.co.kr/learn/courses/30/lessons/42627?language=python3# 

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

- 풀이

* 해당 시점마다 가장 소요시간이 작은 작업을 우선적으로 선택

heapq 사용()

 

1. jobs를 작업이 요청되는 시점기준으로 정렬  >> jobs = [[0, 3], [1, 9], [2, 6]]

2. 만약 해당 sec이하에 요청된 작업들이 있으면, jobs에서 pop해서 queue에 (소요시간, 요청된 시점)의 딕셔너리 형태로 추가

3. 만약 queue에 아무것도 없으면, sec를 +1, 만약 queue와 jobs가 모두 비어있으면, 종료

4. queue에 요청된 작업이 있다면, 그 중 맨앞(최소 소요시간)의 작업을 수행

  - answer에 요청부터 종료까지 소요된 시간 합산

5. 길이로 나눠 평균 반환

 

 

- 코드

import heapq
def solution(jobs):
    length = len(jobs)
    answer, sec, queue = 0, 0, []
    jobs = sorted(jobs)
    heapq.heapify(queue)
    while True:
        if len(jobs) > 0 and jobs[0][0] <= sec:   #해당 sec까지 요청된 작업이 있으면
            temp = jobs.pop(0)
            heapq.heappush(queue, (temp[1], temp[0]))
            continue
        if not queue: #큐에 아무것도 없을 때
            sec += 1
            if len(jobs) == 0:
                break
        else:   #큐 남은작업이 있을 때
            w = heapq.heappop(queue)
            answer += (sec-w[1]) + w[0]
            sec += w[0]
    return int(answer/length)