Python 프로그래머스 디스크컨트롤러 힙

코딩테스트 연습 - 디스크 컨트롤러 | 프로그래머스 (programmers.co.kr)

문제설명은 위의 링크를 확인하면 된다.

일단. CPU 스케줄링 알고리즘 중 SJF (Shortest Job First) 비선점형 알고리즘을 활용한다
CPU스케줄링 참조 : CPU 스케쥴링 알고리즘 : FCFS, SJF, HRN, RR, SRT [과제 : 구현하기] : 네이버 블로그 (naver.com)

큐에 있는 프로세스 중 작업시간이 가장 짧은 프로세스를 실행하는것으로, 그 순간순간에 가장 빨리 끝날녀석을 위주로 실행하는것이다. 

사실 이 스케줄링에도 문제점이 있는데, 작업의 종료시간을 정확히 예측할 수 없다는 것과, 작업시간이 긴 프로세스의 경우, 짧은녀석들에게 밀려서, 한없이 기다리고만 있을 수 있다는 단점이 존재한다 (아사현상). 그렇기에 이 문제를 Aging에이징기법으로 프로세스가 순서를 양보할때마다 카운트해서 한계점까지만 양보하도록 하는 방법을 통해 해결한다. 

간략한 CS에 대한 설명은 여기까지하고, 이제 위 문제를 풀어보자!

from heapq import *
from collections import deque
def solution(jobs):
	jobs = deque(sorted(jobs, key=(lambda x: (x[0],x[1]))))
    waited=0
    n=0
    cnt=jobs[0][0] # 첫 작업 도착시간으로 세팅
    a,b = jobs.popleft()
    hq=[[b,a]]
    while hq or jobs:
        if hq:
            n+=1 # job개수카운트
            jobtime,come = heappop(hq) # 작업시간 , 도착시간
            cnt += jobtime 
            waited+=(cnt-come)
        else:
            cnt+=1
        while jobs:
            if jobs[0][0]<=cnt:
                nextjob = jobs.popleft()
                heappush(hq, [nextjob[1], nextjob[0]])
            else:
                break
        
        print(f'남은 jobs{jobs}\t 현재 HEAP:{hq}, \t\t현재 cnt : {cnt}\t\t현재 waited:{waited}')
    return waited//n

# jobs=[[24, 10], [28, 39], [43, 20], [37, 5], [47, 22], [20, 47], [15, 34], [15, 2], [35, 43], [26, 1]]
jobs=[[0,3],[1,9],[2,6]]
solution(jobs)

힙과 deque를 사용했다. 
Deque를 사용한 이유는 처음 들어온 jobs를 queue형식으로 앞에서부터 꺼내쓰기위해서다. 
굳이 그렇게 안하고 sorted로 역순정렬 후 스택을 활용해도 좋다. (개인취향)

맨처음 heap (hq)에 첫 작업을 넣어주고 시작한다. 제일 먼저도착한, 제일 짧게 끝낼수있는 녀석을 넣어주고 시작한다. 
이후 while문에서는 hq와 jobs가 남아있다면 계속해서 반복하도록 구성하였으며, 

cnt와 waited를 설정하였는데, 
cnt는 순간순간의 초시계라고 생각하면되고, waited는 해당 초에서 heap도착시간을 빼주면서 기록한다. 

if hq에서는 힙에 작업이 있다면, 바로 꺼내서(가장 빨리 끝낼 수 있는 프로세스를) , cnt와 waited를 계산해준다. 
else구문은, hq가 비어있지만, jobs가 남아있는 상황에서 실행된다고 보면된다. 
예를들어 jobs가 [[0,3],[1,9],[20,6]] 이라면, 12초까지 cnt된 후, hp가 비어있는 상태에서 while문의 조건이 cnt보다 남은 작업의 도착시간이 작아야하므로, cnt를 계속 증가시키는것이다. 
그리하여 20초까지 카운트가 진행되면, 다시 작업이 들어가서 마지막작업까지의 계산을 할 수 있게 되는것이다.

while jobs : 구문은 deque로 만들어진 jobs에서, 맨 앞 (빨리도착한순)녀석이 현재 시간 카운트에 맞아떨어진다면 (현재 카운트보다 작거나 같음), 해당하는 프로세스까지 heaq에 넣어주는 기능을 수행하게된다.

위와같은 출력형태를 볼 수 있다.