[Python] 디스크 컨트롤러

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

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

---

 

Point

• 힙 자료구조를 이용해 SJF로 비선점 스케쥴링을 구현해볼 수 있는 문제

Tip

• 시작 전 jobs을 정렬해준다
• 현재 시간에 해당하는 job을 jobs에서 모두 꺼내주고 Min Heap에 저장한다.
• 이때 처리시간이 가장 짧은 순으로(SJF) 정렬된다.
• 컨트롤러에 처리중인 job이 있을 때, 반환시간과 현재시간이 같다면 컨트롤러에서 내리고 총 소요시간을 누적한다
• 컨트롤러가 비었을 때 Min Heap에서 데이터를 꺼내 쓴다.
• 컨트롤러, Min Heap, Jobs 모두 비면 작업을 종료한다.

 

최악 데스트 케이스 메모리

10.4 MB

최악 테스트 케이스 시간

30.14 ms

결과

정확성: 100.0

합계: 100.0 / 100.0

import heapq

def solution(jobs):
    answer = 0
    job_counts = len(jobs)
    
    jobs.sort()
    controller = []
    heap = []
    curr_time = 0
    
    while True:
        while jobs and curr_time == jobs[0][0]:
            arrival_time,processing_time = jobs.pop(0)
            heapq.heappush(heap,[processing_time,arrival_time,processing_time])
   
        if controller:
            turnaround_time = controller[0][0]+controller[0][2]
            if curr_time == turnaround_time:
                assign_time,arrival_time,processing_time = controller.pop(0)
                answer += assign_time+processing_time-arrival_time

        if not controller:
            if heap:
                _,arrival_time,processing_time = heapq.heappop(heap)
                assign_time = curr_time
                controller.append([assign_time,arrival_time,processing_time])
            elif not jobs and not heap:
                break
            
        curr_time += 1
    
    return answer//job_counts

 

문제를 푸는데 도움이 된 테스트 케이스

# Input [[24, 10], [18, 39], [34, 20], [37, 5], [47, 22], [20, 47], [15, 34], [15, 2], [35, 43], [26, 1]]) # Output 74