[프로그래머스/Python] 디스크 컨트롤러

문제

프로그래머스 - 디스크 컨트롤러
💾 문제 링크입니다! 💾

문제 풀이

제가 짠 알고리즘 시나리오는 다음과 같습니다.

1) 대기자가 있다면 heap에서 없다면 task에서 가장 작은 job을 꺼냅니다.
2) job을 수행하면서 흐른 현재 시각과 job이 소요한 시간을 구합니다.
3) task에서 현재 시각보다 먼저 도착한 job들을 대기자 명단인 heap으로 이동시킵니다.
4) 이 때 작업이 요청되는 시점이 아닌 소요 시간 기준으로 정렬합니다.

크게 두 가지가 필요하다고 생각했습니다.

• 작업이 요청되는 시점을 기준으로 정렬한 task
• 현재 시각 전에 도착한 작업들을 작업의 소요시간 순서로 정렬한 heap

task는 작은 순서대로 하나씩 pop할 예정이기 때문에 deque의 leftpop()으로 시간을 조금 더 단축하고자 했습니다.
heap은 들어오는 job들을 작은 순서대로 정렬해주어야하기 때문에 heapq를 사용했습니다.

다른 분들의 풀이를 찾아보다가 깜짝 놀라서 제 답을 리팩토링한 부분이 있는데요.
바로 time과 total을 구하는 부분입니다.

time = max(time + duration, arrived + duration)
total += time - arrived

풀이 초안에서 저는 time을 구하는 부분에서 job이 현재 시각보다 늦게 도착한 경우를 따로 처리했습니다.
그런데 if문이 들어가니 확실히 가독성이 떨어지는 느낌을 받았습니다.
이렇게 max 함수를 이용하면 간단하게 프로세스의 공백 시간을 건너뛸 수 있더군요...
정말 멋진 부분이어서 외워버렸습니다.

소스 코드

짜잔

import heapq
from collections import deque

def solution(jobs):
    heap = []
    total = 0 # 각 작업이 소요한 시간의 합
    time = 0 # 시간
    
    # 작업이 요청되는 시점, 작업의 소요시간 순서로 정렬한 task
    task = deque(sorted([(x[0], x[1]) for x in jobs], key=lambda x: (x[0], x[1])))

    while task or heap:
        # 대기자 있을 경우 heap부터
        if heap:
            job = heapq.heappop(heap)
            arrived, duration = job[1], job[0]
        else:
            job = task.popleft()
            arrived, duration = job[0], job[1]
        
        time = max(time + duration, arrived + duration)
        total += time - arrived
        
        # 대기자 heap으로 이동
        while task:
            if task[0][0] > time:
                break
            job = task.popleft()
            heapq.heappush(heap, (job[1], job[0])) # 소요 시간 기준으로 정렬
        
    return total // len(jobs)