문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42627
참고 자료: https://jhnyang.tistory.com/155
이 문제는 디스크 큐를 컨트롤하는 방식을 직접 구현하는 문제로 디스크에 쓰여질 작업들이 [도착 시간, 작업 시간] 형식으로 제공된다. 실제 디스크 작업이 저런 데이터를 제공할리 만무하지만 이론적으로 어떤 방식이 이득을 볼 수 있는지 확인하기 위해서는 이런 구현도 필요해 보인다.
그럼 이 문제에서 가장 중요한 요소는 heap을 사용하는 것이다. python에서는 heap 자료형을 제공하지는 않지만 heapq 모듈에서 list 자료형을 마치 heap처럼 사용할 수 있도록 기능을 제공하고 있다.
문제에서 요구하는 것은 모든 작업의 최대한 빨리 끝낼 때의 평균 소요 시간이다. 따라서 최대한 빨리 끝내는 방법을 생각해야 하고 평균을 구하는 방법은 쉽게 구현할 수 있을 것 같다. 그런데 문제에는 다음과 같은 제한 사항이 있는 것을 잘 확인하자. 이 제한 사항을 확인하지 않는다면 아마 훨씬 어렵게 풀이를 해야 했을 것이다.
제한 사항: 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.
위 제한 사항을 활용해 최대한 빨리 끝내기 위해서는
1. 일단 먼저 준비된 작업을 수행하기(First Come First Serve)
2. 준비된 작업이 여러 개일 경우, 더 적은 소요 시간을 가진 작업을 먼저 수행하기(Shortest Job First)
위 두 가지 스케줄링 알고리즘을 적절하게 사용하는 로직을 작성하면 된다.
여기서 중요한 점은 heap 연산을 하기 위해서는 대소 연산이 가능해야 하는데 list는 대소 연산이 안된다. 그래서 직접 클래스를 만들어서 __le__, __lt__ 같은 comparable 연산자를 구현해도 되지만, 우리는 시간이 없으니까 heappush()의 좋은 기능을 이용하도록 하자.
heappush(list, (priority, value))와 같이 매개변수를 삽입하면 priority에 따라 heap을 구현해준다. 물론 heappop()할 때에 priority도 그대로 전달되기 때문에 값으로 사용할 수 있다. 걱정하지 말자!
from heapq import heappush, heappop
def solution(jobs):
time = 0
delay_sum = 0
early_heap = []
ready_heap = []
# 일단 먼저 시작하는 작업 힙을 만들자
for start, duration in jobs:
heappush(early_heap, (start, duration))
while early_heap or ready_heap:
# 먼저 시작하는 작업들 중 현재 준비된 작업 힙을 만든다.
while early_heap and early_heap[0][0] <= time:
start, duration = heappop(early_heap)
heappush(ready_heap, (duration, start))
#이제 준비된 작업 중 가장 빨리 끝나는 작업을 실행해준다.
if ready_heap:
duration, start = heappop(ready_heap)
delay_sum += time - start + duration
time += duration
else:
time = early_heap[0][0]
return int(delay_sum/len(jobs))
'''
