프로그래머스 고득점 Kit - 디스크 컨트롤러

 

Problem

https://school.programmers.co.kr/learn/courses/30/parts/12117

프로그래머스

• 우선순위 디스크 컨트롤러 라는 가상의 장치는 아래와 같이 동작한다.
  • 어떤 요청이 들어올 때, 작업의 번호, 요청 시각, 소요 시간을 저장해두는 대기 큐가 있다.
  • 작업의 우선순위가 가장 높은 작업을 큐에서 꺼내 작업한다.
    • 우선순위 => 소요시간이 짧은 것 > 요청 시각이 빠른 것 > 작업의 번호가 작은 것
  •  한번 작업을 시작하면 작업을 마칠때까지 그 작업만 수행한다.
• 모든 요청 작업을 마쳤을때 각 작업에 대한 반환시간은 작업 요청부터 종료까지 걸린 시간을 의미한다.
• 모든 요청의 작업 반환시간의 평균의 정수부분을 return 해라.

 

Input / Output Example

jobs	return
[[0, 3], [1, 9], [3, 5]]	8
[[0, 3], [1, 9], [2, 6]]	9

 

Solution

나는 우선순위 큐(heapq / 힙)와 양방향 큐(deque)를 함께 사용했다.

작업이 들어있는 리스트를 양방향 큐를 사용해 빼내기 쉽게 만들었다.

우선순위 큐는 현재 시각에 맞게 작업을 꺼내 쉽게 처리하려고 사용했다.

 

놀랍게도 해당 문제는 들어오는 값이 정렬이 되어 있지 않다.

먼저 들어오는 작업에 대해 정렬을 진행해야 한다.

나는 들어온 시각을 기준으로 정렬했다.

 

그 다음, 현재 시각에 들어온 작업들을 모두 힙에 넣고, 소요시간과 시각을 계산해 업데이트 했다.

 

여기서 조심해야 하는 점은, 작업이 끝난 시점과 다음 작업이 들어오는 시점이 떨어져 있을 수도 있다는 것이다.

가령 현재 작업은 3초에 끝나는데, 다음 작업은 6초에 들어온다거나..

 

만약 다음 작업이 떨어져 있다면

현재 시각을 다음 작업의 시작 시간으로 옮겨줘야 한다.

 

Code

import heapq
from collections import deque

def solution(jobs):
    size = len(jobs)
    answer = 0
    time = 0
    jobs.sort(key=lambda x:x[0])
    jobs = deque(jobs)
    heap = []
    
    while len(jobs) != 0 or len(heap) != 0:
        while len(jobs) != 0 and jobs[0][0] <= time:
            job = jobs.popleft()
            heapq.heappush(heap, (job[1], job[0]))
        if len(heap) != 0:
            duration, request_time = heapq.heappop(heap)
            time += duration
            answer += (time - request_time)
        else:
            time = jobs[0][0]
    
    return answer//size