[Python] 프로그래머스 - 디스크 컨트롤러(탐욕기법)

프로그래머스 코딩 테스트는 안 하다가, 지식인을 통해서 답변을 하면서 하게 되었네요.

 

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

프로그래머스

 

이 문제에서 핵심은 작업을 관리하는 것을 어떻게 시뮬레이션할 것인가입니다.

현재 태스크에 있는 작업들은 모두 대기상태에서 어떤 것을 먼저 실행하는 것이 좋을까입니다.  태스크에 있는 작업이 한개뿐이라면 전혀 문제가 없겠죠.  하지만 여러개라면, 우선순위를 정해야 합니다.

 

K개의 작업이 있다면, 먼저 수행하는 작업에 의해서 K-1개의 작업이 먼저 수행하는 작업의 실행시간에 의해서 늦어지게 됩니다.  즉, 대기 시간은 먼저 작업하는 작업의 수행 시간이 $t$ms 일때, 전체 작업의 시간은 이로 인해서 $Kt$ms 시간이 추가된다는 것입니다.  그래서 탐욕기법을 이용해서 가장 짧은 수행 시간을 가진 것을 먼저 실행하는 것이 좋습니다.

 

Hard Disk

 

실제로 운영체제에서는 디스크 효율성을 위해서 이와 같은 작업 관리를 합니다.

 

제가 작성한 소스 코드입니다.

#----------------------------------------------------
#    Programmers - Disk Controller
#    By Aubrey Choi
#----------------------------------------------------
from heapq import *
def solution(jobs):
    answer, c, t = 0, 0, 0
    jobs.sort()
    heap = []
    while True:
        while c < len(jobs) and jobs[c][0] <= t:
            heappush(heap, (jobs[c][1], jobs[c][0]))
            c += 1
        if len(heap) > 0:
            d, s = heappop(heap)
            t += d
            answer += t-s
        elif c == len(jobs): break
        else: t = jobs[c][0]
    return answer//len(jobs)