문제 요약
하드디스크는 한 번에 하나의 작업만 수행할 수 있다.
각 작업은 다음 정보를 가진다.
[요청 시각, 소요 시간]하드디스크가 비어 있고 대기 큐에 작업이 있다면, 우선순위가 가장 높은 작업을 꺼내 실행한다.
우선순위는 다음 순서로 결정된다.
- 소요 시간이 짧은 작업
- 요청 시각이 빠른 작업
- 작업 번호가 작은 작업
작업을 한 번 시작하면 끝날 때까지 중단하지 않는다.
모든 작업을 처리했을 때 각 작업의 반환 시간은 다음과 같다.
반환 시간 = 작업 종료 시각 - 작업 요청 시각모든 작업의 평균 반환 시간의 정수 부분을 구해야 한다.
핵심 아이디어
이 문제는 현재 시각까지 요청된 작업 중에서 우선순위가 가장 높은 작업을 계속 선택하는 시뮬레이션 문제다.
우선순위 기준이 다음과 같으므로 우선순위 큐를 사용하면 된다.
소요 시간 -> 요청 시각 -> 작업 번호파이썬에서는 heapq가 최소 힙으로 동작한다.
따라서 힙에 다음 형태로 넣으면 자동으로 원하는 우선순위대로 작업을 꺼낼 수 있다.
(소요 시간, 요청 시각, 작업 번호)작업 번호가 필요한 이유
입력 jobs[i]는 i번 작업을 의미한다.
우선순위 조건에서 소요 시간과 요청 시각이 모두 같다면 작업 번호가 작은 것이 먼저 처리되어야 한다.
따라서 처음에 작업 번호를 함께 저장한다.
indexed_jobs = [
(request_time, duration, job_number)
for job_number, (request_time, duration) in enumerate(jobs)
]요청 시각 순 정렬
작업들을 요청 시각 기준으로 정렬한다.
indexed_jobs.sort()이렇게 하면 현재 시각까지 들어온 작업들을 앞에서부터 차례대로 힙에 넣을 수 있다.
시뮬레이션 흐름
다음 변수들을 사용한다.
time현재 시각이다.
index아직 대기 큐에 넣지 않은 작업 중 가장 앞 작업의 인덱스다.
completed처리 완료한 작업 수다.
total_turnaround모든 작업의 반환 시간 합이다.
heap현재 시각까지 요청된 작업들을 담는 우선순위 큐다.
현재 시각까지 들어온 작업 넣기
현재 시각 time 이하에 요청된 작업은 모두 대기 큐에 들어가야 한다.
while index < n and indexed_jobs[index][0] <= time:
request_time, duration, job_number = indexed_jobs[index]
heapq.heappush(heap, (duration, request_time, job_number))
index += 1문제 조건에서 작업이 끝나는 시각과 요청 시각이 같다면, 요청이 들어온 작업을 먼저 대기 큐에 저장한 뒤 다음 작업을 선택한다고 했다.
따라서 조건은 < time이 아니라 <= time이어야 한다.
힙에서 작업 꺼내기
대기 큐가 비어 있지 않다면 가장 우선순위가 높은 작업을 꺼낸다.
duration, request_time, job_number = heapq.heappop(heap)작업을 수행하면 현재 시각은 소요 시간만큼 증가한다.
time += duration반환 시간은 종료 시각에서 요청 시각을 뺀 값이다.
total_turnaround += time - request_time대기 큐가 비어 있는 경우
아직 처리할 작업은 남아 있지만 현재 시각에 대기 중인 작업이 없을 수 있다.
이 경우 하드디스크는 다음 요청 시각까지 쉬게 된다.
따라서 현재 시각을 다음 작업의 요청 시각으로 이동한다.
time = indexed_jobs[index][0]전체 코드
import heapq
def solution(jobs):
indexed_jobs = [
(request_time, duration, job_number)
for job_number, (request_time, duration) in enumerate(jobs)
]
indexed_jobs.sort()
n = len(jobs)
time = 0
index = 0
completed = 0
total_turnaround = 0
heap = []
while completed < n:
while index < n and indexed_jobs[index][0] <= time:
request_time, duration, job_number = indexed_jobs[index]
heapq.heappush(heap, (duration, request_time, job_number))
index += 1
if heap:
duration, request_time, job_number = heapq.heappop(heap)
time += duration
total_turnaround += time - request_time
completed += 1
else:
time = indexed_jobs[index][0]
return total_turnaround // n시간 복잡도
작업의 개수를 n이라고 하자.
작업을 요청 시각 기준으로 정렬한다.
O(n log n)각 작업은 힙에 한 번 들어가고 한 번 나온다.
O(n log n)따라서 전체 시간 복잡도는 다음과 같다.
O(n log n)공간 복잡도
정렬된 작업 배열과 힙을 사용한다.
O(n)정리
이 문제는 우선순위 큐를 이용한 시뮬레이션 문제다.
풀이 흐름은 다음과 같다.
- 작업 번호를 포함해 작업 정보를 만든다.
- 요청 시각 기준으로 작업을 정렬한다.
- 현재 시각까지 요청된 작업을 힙에 넣는다.
- 힙에서
(소요 시간, 요청 시각, 작업 번호)기준으로 가장 작은 작업을 꺼낸다. - 작업 종료 시각을 갱신하고 반환 시간을 더한다.
- 모든 작업을 처리한 뒤 평균 반환 시간의 정수 부분을 반환한다.
핵심은 힙에 (소요 시간, 요청 시각, 작업 번호)를 넣어 문제의 우선순위를 그대로 구현하는 것이다.
