[프로그래머스] 디스크 컨트롤러 (level3, python)

 

 

🤔 풀이 코드

 

import heapq
from collections import deque

def solution(jobs):
    # jobs : [작업이 요청되는 시점, 작업의 소요시간]
    answer = []
    job_queue = deque(sorted(jobs, key=lambda x : x[0]))
    heap = []
    
    time = 0

    while job_queue or heap:
        # 작업 큐에서 실행가능한 힙으로 이동
        while job_queue and job_queue[0][0] <= time:
            start, during = job_queue.popleft()
            # 소요 시간 (우선순위), 시작 지점
            heapq.heappush(heap, [during, start])
        
        if heap:
            use_time, start = heapq.heappop(heap)
            cost = use_time + time - start
            answer.append(cost)
            time += use_time
        else:
            time += 1
            
    return sum(answer) // len(answer)

 

 

🤔 문제 풀이

 

주의해야 할 점이 좀 많은 문제였습니다.

- 주어지는 job이 작업이 요청되는 시점으로 정렬되어 들어오지 않았다는 점

- 작업의 요청 부터 종료까지 걸리는 시간의 평균을 계산하기 위해서, 디스크 컨트롤러가 일하고 있지 않을 때는 계산하면 안된다는 점

- 우선순위는, 소요시간이 짧을 수록 높습니다.

- 작업이 실행되고 있지 않은 경우에는 먼저 요청이 들어온 작업부터 수행합니다. (소요시간이 우선순위, 다음 우선순위는 요청이 들어온 시간)

 

따라서 우선 작업 요청 시점으로 정렬한 후, queue에 보관했습니다.

현재 디스크 컨트롤러가 실행될 수 있는 작업들에 대해서는 heap에 보관을 하고,

현재 시간을 time이라는 변수로 관리했습니다.

 

아직 요청시간이 되지 않아 queue에 남아있거나 아직 실행이 가능은 하지만 아직 실행하지 않은 작업이 heap에 남아있다면 계속해서 로직을 반복합니다.

 

우선, job_queue에서 실행 가능한 작업을 모두 뽑아냅니다. heap에 넣을 때는, 우선순위를 고려해서 넣어야하는데 생각보다 단순하게도, 우선순위는 '소요 시간'이고, 차우선순위는 요청이 들어온 시간입니다.

 

만약 heap에서 실행할 수 있는 작업이 있다면,

heap에서 꺼내어 소요 시간을 계산하고, 현재 시간을 소요 시간만큼 갱신합니다.

만약 실행할 수 있는 작업이 없다면, time을 1초 늘려 반복합니다.