[프로그래머스 level3 디스크 컨트롤러] heapq 사용하기!

해결해야하는 문제는 다음과 같았다.

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

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

 

 

우선 heapq 란, 파이썬에서 제공하는 내장함수로, 정렬된 상태로 데이터를 저장할 수 있도록 해준다.

예를 들어, jobs를 낮은 순으로 정렬되도록 하고 싶은 경우(최소 힙) -> heapq.heapify(jobs)를 통해 heap으로 저장될 수 있도록 한다.

heapq를 활용해 push 하고 싶은 경우, heapq.heappush(wait_queue, 원소) 형태로 push 할 수 있고,

heapq를 활용해 pop 하고 싶은 경우, heapq.heappop(wait_queue)와 같은 형태로 pop 할 수 있다.

heapq를 통해 pop을 하는 경우, 가장 작은 원소를 pop 시켜준다!!!

 

 

이 문제에 접근하기 위해서 많은 생각을 했었는데 처음으로 떠오른 것은 운영체제 시간에 cpu scheduling 의 sjf 방법이 떠올랐다.

non-preemptive 하여 실행 도중에 다른 것이 실행되지는 않지만

현재 시간까지 온 job 들 중 실행시간이 짧은 것을 우선적으로 처리하는 것이 sjf 방법이었다. 이 방법을 활용하면 이 문제도 풀 수 있을 것 같았다.

 

시간과 걸리는 시간과 요청받은 시간을 저장하는 time, req_time, during_time을 만들고, 현재 time 시간 안에 요청이 들어왔는데 아직 실행되지 않은 경우 wait_queue에 저장하였다.

 

wait_queue나 jobs 가 비어있지 않은 경우, 아직 실행되지 않은 job 이 있다는 뜻이므로 while문을 반복하도록 하였다.

1. jobs가 비어 있지 않은 경우, request time이 현재 시간보다 작다면 pop하여 wait queue에 저장되도록 하였다. 

(jobs는 heapify를 통해 최소힙으로 구현되어 있기 때문에 request time이 작은 순서로 정렬되어 있다는 점을 활용)

-> 여기서 wait queue는 during time 순서로 저장될 수 있도록 하기 위해 [::-1]로 during_time과 req_time 원소의 순서를 바꾸어주었다.

 

2-1. wait queue가 비어있지 않은 경우, waitqueue의 원소를 pop 한다. 시간은 현재 시간부터 job을 처리하는 시간을 더해준만큼 흐르도록 하고 answer에는 (실행이 마무리 된 시간) - (요청이 온 시간) 을 더해준다.

 

2-2. waitqueue가 비어 있는데 수행해야 하는 jobs는 남아 있는 경우, waitqueue에 jobs를 넣어주고, 

time은 ((요청이 온시간) - (현재 시간)) + (실행시간)을 더하여 update 해준다.

그리고 answer는  (실행이 마무리 된 시간) - (요청이 온 시간) 을 더해준다.

 

2-3. waitqueue도 비고, jobs도 빈 경우에는 더이상 처리할 일이 없으므로 break 한다.

 

 

마지막으로 총  (실행이 마무리 된 시간) - (요청이 온 시간) 의 평균을 구하기 위해 answer //= 총 job 개수 를 하여 return 해준다.

 

 

이러한 아이디어를 바탕으로 작성한 코드는 다음과 같다.

 

import heapq

def solution(jobs):
    answer = 0
    jobs_n = len(jobs)
    # 낮은 순으로 정렬된다. (최소 힙) 
    heapq.heapify(jobs)
    wait_queue = []
    time,req_time,during_time=0,0,0

    while wait_queue or jobs:
        while jobs:
            if jobs[0][0]<time :
                heapq.heappush(wait_queue,heapq.heappop(jobs)[::-1])
            else :
                break
        
        
        if wait_queue:
            during_time,req_time = heapq.heappop(wait_queue)
            time += during_time
            answer += (time - req_time)
        else :
            if jobs :
                heapq.heappush(wait_queue,heapq.heappop(jobs)[::-1])
                during_time,req_time = heapq.heappop(wait_queue)
                time += (req_time-time)+during_time
                answer += (time-req_time)
            else :
                break
        
        
    answer //= jobs_n
    return answer