문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42627
import heapq
def solution(jobs): # [요청 시각, 소요 시간]
# 요청 시각 기준 정렬
jobs.sort()
curr_time = 0 # 현재 시간
total = 0 # 총 반환시간
idx = 0 # jobs 인덱스
complete_count = 0 # 처리 완료 개수
heap = [] # 대기 큐
while complete_count < len(jobs): # 모든 작업 끝날 때까지
# 현재 시간까지 요청된 작업 모두 힙에 저장
while idx < len(jobs) and jobs[idx][0] <= curr_time:
request, duration = jobs[idx]
heapq.heappush(heap, (duration, request)) # 튜플 형태로 heap에 저장(1순위: 소요시간, 2순위: 요청 시각)
# 작업 번호는 고려x -> 소요시간, 요청시각 같으면 평균 반환시간 동일
idx += 1 # 다음 작업 번호
# 힙에서 꺼내서 작업 실행
if heap:
duration, request = heapq.heappop(heap)
curr_time += duration
total += curr_time - request # 반환 시간 = 종료 시각 - 요청 시각
complete_count += 1
else: # 처리할 작업이 아직 안들어왔으면 현재 시간을 다음 요청 시각으로 점프
curr_time = jobs[idx][0] # 그 다음 작업 번호의 요청 시각
return total // len(jobs)핵심 1
jobs 리스트는 요청 시각 기준으로 정렬한 후, heap에 '소요 시간'과 '요청 시각'을 따로 넣어줘야한다. 이때 heap 자료구조를 사용하는 이유는, 소요시간이 최소인 아이템을 가장 먼저 뽑아야하기 때문이다.
우선순위: 소요시간 > 요청 시각 > 아이템 번호
heapq.heappush(heap, (duration, request))
튜플에 작업 번호 idx를 넣지 않았다. 그 이유는 소요시간과 요청시각이 같은 작업이면 완전히 동일한 작업이기 때문에 그것들 중에서 어떤 것을 먼저 수행해도 반환 시간(종료 시각 - 요청 시각)의 평균은 같기 때문이다.
핵심 2
curr_time을 기준으로 작업을 수행하고, curr_time을 점점 이동시킨다.
1) heap에 저장
2) heap에서 꺼내서 작업 수행(duration이 최소인 아이템부터 꺼내진다)
요청 시각 <= 현재 시각 인 아이템들을 대상으로 1번 작업을 먼저 수행한 후, 2번을 수행한다.
cf) 요청 시각:
jobs[idx][0]
여기서idx는 jobs의 작업 번호이다.
만약 해당 조건에 해당하는 아이템이 없어서 heap 비었으면 curr_time을 다음 작업 번호의 요청 시각으로 갱신해준다.
(curr_time = jobs[idx][0])
핵심 3
하나의 작업을 완료하면 curr_time에 duration만큼 더해서 갱신해주고 반환 시간(total)을 계산해서 갱신해준다.
접근하기 어려웠던 점
jobs 리스트를 가지고 어떻게 우선순위 큐를 구현해야하는지가 어려웠다.
일단 2차원 배열 정렬 개념이 머릿속에 잡혀있지 않았고, 요청 시각 순으로 정렬된 jobs를 작업 목록으로 활용하고 heap은 대기 큐로 활용할 생각을 못했다.
또한 jobs는 [요청 시각, 소요 시간] 인데 이 상태로 힙에 저장하면 소요 시간이 가장 우선순위가 높다는 문제 조건을 충족할 수 없다. 따라서 heap에는 (소요 시간, 요청 시각) 처럼 순서를 바꾼 튜플을 한 아이템으로 저장해야 했다.
