프로그래머스 Lv.3: 디스크 컨트롤러 - Python 풀이

문제 설명

프로그래머스

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 이 문제에서는 우선순위 디스크 컨트롤러라는 가상의 장치를 이용한다고 가정합니다. 우선순위 디스크 컨트롤러는 다음과 같이 동작합니다.

1. 어떤 작업 요청이 들어왔을 때 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두는 대기 큐가 있습니다. 처음에 이 큐는 비어있습니다.
2. 디스크 컨트롤러는 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면 가장 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 이때, 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높습니다.
3. 하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행합니다.
4. 하드디스크가 어떤 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면 하드디스크가 작업을 마치자마자 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 또, 하드디스크가 어떤 작업을 마치는 시점에 다른 작업이 들어오지 않더라도 그 작업을 마치자마자 또 다른 작업을 시작할 수 있습니다. 이 과정에서 걸리는 시간은 없다고 가정합니다.

예를 들어

• 0ms 시점에 3ms가 소요되는 0번 작업 요청
• 1ms 시점에 9ms가 소요되는 1번 작업 요청
• 3ms 시점에 5ms가 소요되는 2번 작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 다음과 같습니다.

이 요청을 우선순위 디스크 컨트롤러가 처리하는 과정은 다음 표와 같습니다.

시점	하드디스크	대기 큐	디스크 컨트롤러
0ms		[]
0ms		[[0번, 0ms, 3ms]]	0번 작업 요청을 대기 큐에 저장
0ms	0번 작업 시작	[]	대기 큐에서 우선순위가 높은 0번 작업을 꺼내서 작업을 시킴
1ms	0번 작업 중	[[1번, 1ms, 9ms]]	1번 작업 요청을 대기 큐에 저장
3ms	0번 작업 완료	[[1번, 1ms, 9ms]]
3ms		[[1번, 1ms, 9ms], [2번, 3ms, 5ms]]	2번 작업 요청을 대기 큐에 저장
3ms	2번 작업 시작	[[1번, 1ms, 9ms]]	대기 큐에서 우선순위가 높은 2번 작업을 꺼내서 작업을 시킴
8ms	2번 작업 완료	[[1번, 1ms, 9ms]]
8ms	1번 작업 시작	[]	대기 큐에서 우선순위가 높은 1번 작업을 꺼내서 작업을 시킴
17ms	1번 작업 완료	[]

모든 요청 작업을 마쳤을 때 각 작업에 대한 **반환 시간(turnaround time)**은 작업 요청부터 종료까지 걸린 시간으로 정의합니다. 위의 우선순위 디스크 컨트롤러가 처리한 각 작업의 반환 시간은 다음 그림, 표와 같습니다.

작업 번호	요청 시각	작업 종료 시각	반환 시간
0번	0ms	3ms	3ms(= 3ms - 0ms)
1번	1ms	17ms	16ms(= 17ms - 1ms)
2번	3ms	8ms	5ms(= 8ms - 3ms)

우선순위 디스크 컨트롤러에서 모든 요청 작업의 반환 시간의 평균은 8ms(= (3ms + 16ms + 5ms) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 정수 배열 jobs가 매개변수로 주어질 때, 우선순위 디스크 컨트롤러가 이 작업을 처리했을 때 모든 요청 작업의 반환 시간의 평균의 정수부분을 return 하는 solution 함수를 작성해 주세요.

---

제한 사항

• 1 ≤ jobs의 길이 ≤ 500
• jobs[i]는 i번 작업에 대한 정보이고 [s, l] 형태입니다.
  • s는 작업이 요청되는 시점이며 0 ≤ s ≤ 1,000입니다.
  • l은 작업의 소요시간이며 1 ≤ l ≤ 1,000입니다.

---

입출력 예

jobs	return
[[0, 3], [1, 9], [3, 5]]	8

풀이 과정

1. 일단 요청 시각 순으로 정렬합니다. 소요시간이 아무리 작아도 요청이 들어오지 않은 작업은 실행할 수 없습니다.
2. 정렬한 작업을 하나씩 확인하면서 요청 시간이 현재 time 이하라면 (= 현재 수행 가능한 작업) 다음으로 확인해야 할 것은 소요 시간입니다. 소요 시간이 최솟값인 작업을 찾고 이를 먼저 실행해야 합니다.
3. 현재 time 이하의 요청 시간을 가지는 작업 중 소요 시간이 최솟값인 작업 A를 찾아 돌리고 나면 time은 A의 소요 시간만큼 더해지고, A의 turnaround time은 현재 time에서 A의 요청 시간을 뺀 값입니다. 이를 반영하고 2번으로 돌아가 반복합니다. 모든 작업을 실행할 때까지.

며칠 전에 풀었던 백준 ‘보석 도둑’이랑 거의 비슷한 문제처럼 느껴지네요.

요청 시간을 기준으로 하는 최소힙과 소요 시간을 기준으로 하는 최소힙을 각각 가지고 문제를 풀이하면 됩니다.

정답 코드

import heapq as hq

def solution(jobs):
    answer = 0
    time = 0
    job_infos = []
    # s: 요청 시간을 기준으로 최소힙을 구성
    for i, (s, l) in enumerate(jobs):
        # s: 요청 시간, l: 소요 시간, i: 작업 번호
        hq.heappush(job_infos, (s, l, i))
    # 각 작업에 대한 반환 시간 초기화
    turnaround_times = [0] * len(jobs)
    # l: 소요 시간을 기준으로 구성될 최소힙 생성
    l_min_heap = []
    # 모든 작업을 실행할 때까지 반복
    while job_infos or l_min_heap:
        # 아직 실행하지 않은 작업이 있고, 최소 요청 시간이 현재 시간 이전이라면
        if job_infos and job_infos[0][0] <= time:
            # 현재 실행할 수 있는 작업으로 판단
            first = hq.heappop(job_infos)
            # 현재 실행 가능 작업 중 소요 시간이 최솟값인 작업을 구하기 위해
            # 소요 시간을 기준으로 최소힙 구성
            hq.heappush(l_min_heap, (first[1], first[0], first[2]))
        else:
            # 현재 실행 가능한 작업 있는데 소요 시간 확인 중
            if l_min_heap:
                # 최소 소요 시간 작업을 pop
                l_min = hq.heappop(l_min_heap)
                # 현재 시간에 소요 시간을 더한다
                time += l_min[0]
                # 작업 번호에 맞게 반환 시간 계산해서 저장
                # 반환 시간은 현재 시간 - 해당 작업 요청 시간이다
                turnaround_times[l_min[2]] = time - l_min[1]
            # 현재 시간에 실행 가능한 작업이 아예 없음
            else:
                # 시간을 땡긴다~ 최소 요청 시간과 동일한 시간으로
                time = job_infos[0][0]
    # 반환 시간의 평균 계산
    answer = sum(turnaround_times) // len(turnaround_times)
    return answer

 

이상입니다.