이 문제에서는 전체 요청을 처리 해야 하지만, 그와 동시에, 최소시간안에 처리해야 하는 문제입니다.
따라서, 짧은 요청을 먼저 실행해야, 아직 실행되지 않은 요청들이 대기하는 시간이 줄어들게 되서,
최소시간안에 처리하게 되는 것입니다.
a 0ms, 3ms
b 0ms, 2ms
c 0ms, 1ms
이렇게 3개의 요청을 받았다고 하면 (여기서 부터는, 요청을 job으로 작성하겠습니다.)
3개의 요청은 모두 0ms 에 시작할 수 있습니다. (job의 시작시간을 start_time으로 작성하겠습니다.)
start_time이 모두 0ms 로 같기 때문에 3개 job 모두 처음부터 실행할 수 있습니다.
그러면 a, b,c 3가지 중에 어떤 것을 먼저 실행할 지 선택해야 합니다.
a를 선택했다고 가정하면, a 는 3ms 동안 실행합니다.
b 와 c 는 a를 실행하는 3ms 동안 b와 c 모두 3ms 동안 대기 해야 합니다.
하지만, c 를 선택했다면, a 와 b는 c의 실행시간(duration으로 작성하겠습니다) 1ms 동안만
기다리게 됩니다. 따라서, c를 선택해야 합니다.
즉, 가장 먼저 실행해야하는 job은 start_time이 가작 작은 job이고, start_time 가장 작은
job이 여러개가 있다면, 그중에서는 duration이 가장 작은 job을 선택해야,
전체 job의 대기시간을 가장 작게 할 수 있습니다.
여기까지 문제를 풀고 파이썬 코드를 작성해보면 아래와 같습니다.
def my_sort(a, b):
if a[0] < b[0]:
return -1
elif a[0] > b[0]:
return 1
else: # a[0] == b[0]
if a[1] < b[1]:
return -1
elif a[1] > b[1]:
return 1
else: # a[1] == b[1]
return 0
def solution(jobs: List):
current_time = 0 # 현재 시간
count = len(jobs) # job의 개수
answer = 0 # 전체 걸린 시간
jobs = sorted(jobs, key=cmp_to_key(my_sort))
# my_sort를 사용해서 정렬하구요, jobs 를 start_time이 작은 순서로 정렬하고,
# start_time이 같은 job은 duration이 작은 순서로 정렬 합니다.
job은 start_time이 정해저 있기 때문에, 현재 시간을 가리키는
current_time 변수가 필요합니다. start_time <= current_time 인 job 만 실행할 준비가 된 것입니다.
def my_sort(a, b):
if a[0] < b[0]:
return -1
elif a[0] > b[0]:
return 1
else: # a[0] == b[0]
if a[1] < b[1]:
return -1
elif a[1] > b[1]:
return 1
else: # a[1] == b[1]
return 0
def solution(jobs: List):
current_time = 0 # 현재 시간
count = len(jobs) # job의 개수
answer = 0 # 전체 걸린 시간
jobs = sorted(jobs, key=cmp_to_key(my_sort))
# my_sort를 사용해서 정렬하구요, jobs 를 start_time이 작은 순서로 정렬하고,
# start_time이 같은 job은 duration이 작은 순서로 정렬 합니다.
while len(jobs) > 0:
is_idle: bool = True
while len(jobs) > 0 and jobs[0][0] <= current_time:
is_idle = False
[start_time, duration] = jobs.pop(0)
if is_idle:
current_time += 1
return int(answer / count)
is_idle 변수는 current_time에서 아무 job도 실행되지 않았다면, current_time을 1 증가
시켜주는 역할 을 합니다.
실행할 준비가 된 job들을 jobs 에서 하나씩 꺼내올 수 있게 되었습니다. 하지만 꺼내온
job들도 duration 짧은 job 부터 실행해야 하는데요, 여기서 heap 자료구조를
사용해서, duration이 짧은 순서로 job를 정렬합니다.
def my_sort(a, b):
if a[0] < b[0]:
return -1
elif a[0] > b[0]:
return 1
else: # a[0] == b[0]
if a[1] < b[1]:
return -1
elif a[1] > b[1]:
return 1
else: # a[1] == b[1]
return 0
def solution(jobs: List):
current_time = 0 # 현재 시간
count = len(jobs) # job의 개수
answer = 0 # 전체 걸린 시간
jobs = sorted(jobs, key=cmp_to_key(my_sort))
# my_sort를 사용해서 정렬하구요, jobs 를 start_time이 작은 순서로 정렬하고,
# start_time이 같은 job은 duration이 작은 순서로 정렬 합니다.
heap = []
while len(jobs) > 0 or len(heap) > 0:
is_idle: bool = True
while len(jobs) > 0 and jobs[0][0] <= current_time:
is_idle = False
[start_time, duration] = jobs.pop(0)
heapq.heappush(heap, [duration, start_time])
if len(heap) > 0:
is_idle = False
[duration, start_time] = heapq.heappop(heap)
answer += (current_time - start_time)
answer += duration
current_time += duration
if is_idle:
current_time += 1
return int(answer / count)
start_time <= current_time 인 job을 꺼내서, heap 에 duration과 start_time을 함께
넣어주게되면, heapq.heappop()에서 duration이 짧은 job 부터 리턴 해 줍니다.
현재시간은 current_time 에서 start_time을 빼주면, 이 job 이 기다린 시간을
계산해서, answer에 더해주고, 이 job의 duration도 함께 answer에 더해 줍니다.
마지막으로 answer / count 를 한 뒤에, 소수 점을 제외하기 위해서 int() 를 사용합니다.
