프로그래머 (programmers) 디스크 컨트롤러 파이썬 정답 (힙)

문제 링크

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

프로그래머스

코드 중심 개발자 채용. 스택 기반 포지션 매칭 프로그래머스 개발자를 위한 커스텀 프로파일을 등록하고 나와 기술의 궁합이 잘 맞는 기업을 매칭합니다.

문제 정답

입출력 예

직업	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초 증가하기 때문이다.

따라서, 빨리 종료하는 잡을 우선 처리하지 않으면, 총 대기 시간이 짧아지는 것을 알 수 있다.

간단하게 생각하면 큐에 복수의 아이템이 함께 존재하면, 동시에 대기 시간이 늘어나므로,

큐에 있는 아이템의 개수를 줄인다고 생각하면 된다.

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

jobs를 시작 가능 시간이 짧은 것에서 힙에 넣습니다.

(초기화)
실행 가능한 작업을 별도로 힙에 던집니다.

이 힙은 실행 시간이 짧은 것부터 시작합니다.
3의 힙에서 가장 빨리 끝나는 작업을 하나 처리한 후 나머지 작업을 다시 힙에 넣고 2를 반복합니다.