[프로그래머스] 디스크 컨트롤러 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42627

코딩테스트 연습 - 디스크 컨트롤러

 

OS의 스케쥴링 정책 중 SJF에 대한 알고리즘문제이다

SJF는 현재 작업큐에서 가장 실행시간이 짧은 작업을 우선적으로 처리하는 것이다.

현재 시각을 기준으로 대기열에서 시작 시각이 현재 시각보다 작거나 같은 작업을 작업 큐에 넣고

작업 큐에서는 실행시간이 짧은 것을 처리하는 것이다.

 

문제의 jobs를 대기열로 그대로 사용하기 위해 요청시각을 기준으로 내림차순으로 정렬하고 끝에서부터 pop한다.

 

대기열과 작업큐가 다 비워질때까지 반복문을 돌리는데

이때 현재 시각보다 요청 시각이 작은 작업을 작업큐로 옮기고

작업큐에 작업이 들어 있다면 현재 시각을 처리시간만큼 더해주고 총 처리시간을 더해준다.

총 처리시간은 현재 작업의 처리시간 + 대기 시간이다.

대기시간은 현재 시각 - 작업의 요청 시각을 빼준값이다.

 

만약 작업큐에 작업이 없다면 현재 시각을 1씩 증가 시켜줘야한다.

이것을 안해서 틀리고 있었다.

 

import heapq

def solution(jobs):
    cnt = len(jobs)
    jobs.sort(reverse=True)
    
    pq = []
    now = 0
    answer = 0
    while jobs or pq:
        while jobs and jobs[-1][0] <= now:
            heapq.heappush(pq,(jobs[-1][1],jobs[-1][0]))
            jobs.pop()
        if pq:
            t,req = heapq.heappop(pq)
            answer += t+now-req
            now += t
        else:
            now += 1
    return answer//cnt