프로그래머스(programmers) 디스크 컨트롤러 python 정답 [힙(heap)]

프로그래머스(programmers) 디스크 컨트롤러 python 정답 [힙(heap)]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

문제 정답

입출력 예

jobs	return
[[0, 3], [1, 9], [2, 6]]	9

정답 코드

import heapq
import math
def solution(jobs):
    heapq.heapify(jobs)
    current = 0
    answer = []
    n = len(jobs)
    while jobs:
        # 타임 점프 - 작업이 실행 가능한 시간으로 점프한다.
        if current <= jobs[0][0]:
            current = jobs[0][0]
        # 실행 가능한 작업들을 추린다.
        targets = []
        while jobs and jobs[0][0] <= current:
            c,d = heapq.heappop(jobs)
            # 힙은 오름차순 이므로 D를 배열의 앞에 위치한다.
            heapq.heappush(targets,[d,c])
        # 시간을 갱신한다. 힙은 오름차순 이므로 D가 작은 것부터 처리한다.
        nextD,nextC = heapq.heappop(targets)
        current += nextD
        answer.append(current-nextC)
        for d,c in targets:
            heapq.heappush(jobs,[c,d])
                                                    
        
    
    return math.floor(sum(answer) // n)

문제 해설

대기시간 줄이기

작업의 요청 시간부터 걸린 시간의 합을 최소화해야 한다.

같이 시작할 수 있는 4ms, 7ms 작업이 있다 생각해보자.

만약 4ms부터 시작하면 4ms + 11ms =>15ms가 된다.

만약 11ms부터 시작하면 7ms + 11ms => 18ms가 된다.

7ms를 먼저 처리하면 4ms와 동시에 대기열에 존재하는 시간이 3초 증가하기 때문이다.

 

따라서 빨리 종료되는 작업을 우선 처리해야 총 대기시간이 줄어든다는 것을 알 수 있다.

간단하게 생각하면 대기열에 여러 아이템이 같이 존재하면, 동시에 대기시간이 늘어나므로,

대기열에 있는 아이템의 갯수를 줄인다 라고 생각하면 된다.

 

로직은 코드의 주석을 참고하면 된다만, 핵심은 다음과 같다.

1. jobs를 시작 가능 시간이 짧은 것부터 힙에 넣는다. (초기화)
2. 실행 가능한 작업을 따로 힙에 추린다. 이 힙은 실행 시간이 짧은 것부터 먼저 들어간다.
3. 3의 힙에서 가장 빨리 끝나는 작업을 하나 처리한 뒤 남은 작업들을 다시 힙에 넣고 2를 반복한다.