[프로그래머스] 디스크 컨트롤러
문제
하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.
A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.
각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)
제한사항
- jobs의 길이는 1 이상 500 이하입니다.
- jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
- 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
- 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
- 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.
입출력 예
문제에 주어진 예와 같습니다.
- 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
- 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
- 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.
풀이
만약 작업이 요청되는 시점이 같은데 작업의 소요시간이 더 긴걸 처리한다면 작업의 요청부터 종료까지 걸린 시간의 평균은 더 길어지게 된다.
따라서 이번 문제의 목적은 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 것이기 때문에 요청이 들어온 작업 중 “작업의 소요시간”이 가장 작은 작업들부터 처리해야만 한다.
즉 준비된 작업들은 작업의 소요시간을 기준으로 오름차순으로 정렬되어야 한다는 것이다.
시점에 따라 준비된 작업들이 새로 들어오기 때문에 이런 경우에 쓰면 좋은 자료구조는 바로 Heap이다.
Heap은 이진트리구조 기반으로 입력과 동시에 요소가 오름차순으로 정렬되는 특성이 있기 때문이다.
작성할 코드의 Flow를 정리하면 다음과 같다.
- 작업 요청 시점을 기준으로
jobs를 정렬한다. - jobs의 요소가 없을 때 까지 아래의 작업을 반복한다.
- jobs에 남은 요소가 있고 jobs의 작업 요청시간이 현재 시점
t보다 작거나 같으면 아래를 반복한다.- jobs의 성분을 pop하고, [작업소요시간, 작업요청시간]을 heap에 push한다.
- heap에 성분이 있다면 해당 성분을 pop하고 소요시간을 t에 더해주고, 현재시간 - 작업요청시간을 뺀 것을 answer에 더해준다.
- heap에 성분이 없다면 t += 1을 한다.
- jobs에 남은 요소가 있고 jobs의 작업 요청시간이 현재 시점
- 2번이 끝나고 나면 heap에 성분이 남아있는 동안 아래를 반복한다.
- heap의 성분을 pop하고 소요시간을 t에 더해주고, 현재시간 - 작업요청시간을 뺀 것을 answer에 더해준다.
- answer에 작업의 개수를 나눠 평균을 구하고 반환한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import heapq
def solution(jobs):
# sorting이 되서 나오는건줄..
jobs.sort()
t = 0
answer = 0
len_j = len(jobs)
heap = []
while jobs:
while jobs and jobs[0][0] <= t:
request_time, task_time = jobs.pop(0)
heapq.heappush(heap, [task_time, request_time])
if heap:
task_time, request_time = heapq.heappop(heap)
t += task_time
answer += t - request_time
else:
t += 1
while heap:
task_time, request_time = heapq.heappop(heap)
t += task_time
answer += t - request_time
return int(answer / len_j)