[프로그래머스] 디스크 컨트롤러 | 파이썬 (💡 SJF 스케줄링 구현하기)

문제 설명

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

 

문제 풀이

작업의 요청부터 종료까지 걸린 시간의 평균을 최소로 만들어야하는, 즉 SJF(Shortest-Job-First) 스케줄링을 비선점형 방식으로 구현하는 문제였다. 마침 운영체제에서 스케줄링 기법을 공부하고 있었던 터라 반가웠던 문제❕

 

스케줄링에 관한 내용은 아래에서 확인

[운영체제] 4. CPU 스케줄링 | KOCW 2017 이화여대 반효경 교수님

 

전체 코드

import heapq

def solution(jobs):
    n = len(jobs)
        
    now = 0     # 현재 시간
    answer = 0  # 소요시간의 합
    count = 0   # 처리량
    ready_queue = []
    
    while count < n:
        for i in range(n):
            # 처리 되지 않은 작업이면서 요청 시간이 현재 시간보다 작은 경우
            if jobs[i] and jobs[i][0] <= now:
                heapq.heappush(ready_queue, (jobs[i][1], jobs[i][0]))
                # Ready Queue에 들어간 작업은 False로 처리
                jobs[i] = False 
        
        # Ready Queue에 처리할 작업이 있는 경우
        if ready_queue:
            size, request = heapq.heappop(ready_queue)
            
            # 처리 후 시간을 현재 시간으로 갱신
            now += size
            answer += (now - request)
            count += 1
        else:
            now += 1
    return answer // n

 

✔ Ready Queue에 처리할 작업이 없어도 시간은 흘러가야 한다.

= 반복문 내 now 변수를 사용하자❕

* 처리할 작업이 있으면 소요시간을 더해 갱신하고 없으면 1 더하기

 

✔ 각 시점마다 작업의 소요시간이 가장 작은 작업을 처리해야 한다.

= 우선순위 큐를 사용하자❕

* 파이썬의 heapq 라이브러리 사용