[PROGRAMMERS] 힙(Heap) : 디스크 컨트롤러 Python

이 문제는 작업이 들어오는 시간과, 그 작업이 걸리는 시간을 알려주는 이차원 배열이 주어질 때 각 작업이 요청부터 종료까지 걸린 평균시간이 가장 적은 답을 구하는 문제이다.

살짝 보면 Greedy문제 같지만, 문제에서 제공된 예시들을 봤을 때,  CPU 스케줄링의 SPN방식과, SRN 방식이 떠올랐다. 물론 문제에서 선점, 비선점에 대한 설명을 해주지 않아 어떤 방식으로 해야 할지 고민했지만, 우선 구현이 쉬워 보이는 SPN방식으로 문제를 풀어보았고 다행히 정답이 나왔다.

디스크컨트롤러 문제설명 (출처 : 프로그래머스)

SPN방식이란 기본적으로는 작업이 들어온 시간을 기준으로 작업을 처리하지만, 작업을 처리하는 중에 들어온 작업들에 대해서는, CPU요구량이 적은 것 부터 처리하는 비선점 방식의 스케줄링이다.

즉, 이문제의 요구사항과 같이, 기본적으로는 들어오는 순서대로 작업을 처리하고 작업을 처리하는 도중에 들어오는 작업들에 대해서는 소요시간이 적은 것부터 처리를 해주었다. 나는 이 작업을 코드로 해주기 위하여 힙 자료구조를 사용했다.

나는 이를 구현하기위해 아래의 방법을 사용했다.
1. flag 를 통하여 현재 힙의 처리해야 할 작업들이 있는지 없는지 확인한다.
2. 처리해야할 작업이 없다면 시간순으로 들어오는 가장 빨리 끝나는 작업을 처리한다.
3. 위 과정을 처리하면서 heap의 그 시간동안 작업들이 들어와야 하기 때문에 flag를 사용하여 힙의 작업들을 넣어야 한다고 알려준다,
4. 힙의 넣어야 할 작업들을 모두 넣고, 더 이상 넣을 게 없다면 힙에서 최소 시간이 소요되는 작업을 처리한다.
5. 만약 힙의 넣어야 할 작업들이 없다면 flag를 다시 초기화한다

그리고 이를 코드로 나타내면, 

디스크컨트롤러 문제풀이

이렇게 된다.

마지막의 while문은 모든 jobs들을 확인했을 때, Q의 남아있는 작업들을 모두 처리해주는 역할을 한다.

확실히 다른 사람들의 코드를 보다가 나의 코드를 보면 부족한점이 많이 느껴진다. 꾸준히 연습해서 빨리 실력을 발전시키고 싶다.

문제 출처 : 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/42627

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