설명

프로그래머스의 디스크 컨트롤러 문제다.

하드 디스크 드라이브에서 헤드가 움직이는 알고리즘을 구현하라는 것 같은데 왠지 프로세스 스케줄링(SJT)이 생각나는 문제다. 문제에서 명시적으로 언급하지 않아서 헷갈렸는데 대기 큐에 있는 작업 중 가장 작은 작업시간을 가진 작업을 처리하도록 구현하는 문제였다.

각 작업의 요청부터 처리 완료까지 걸린 시간(RTT)의 평균이 가장 작도록 하는 문제로 SJT에서 발생할 수 있는 무한 대기같은 상황은 고려하지 않는다.

풀이

편의를 위해 0초부터 타이머를 재며 각 시간대의 작업을 우선순위 큐에 삽입하며 현재 진행중인 작업이 다 끝나면 큐에서 가장 작은 처리시간을 가진 작업을 추출하여 처리한다.

역시 이번에도 파이썬의 heapq 모듈을 활용하였으며 코드는 다음과 같다.

import heapq
import collections


def solution(jobs):
    return_times = [] # 각 작업의 RTT를 저장.
    timed_jobs = collections.defaultdict(list) # 각 시간대 별 작업 목록.
    waiting_jobs = [] # 작업 대기열.

    # 각 시간대 별 작업을 사전에 저장.
    for requested_time, required_time in jobs:
        timed_jobs[requested_time].append(required_time)
    
    # 시간대를 나타내는 타이머.
    current_time = 0
    # 가장 늦게 들어오는 작업의 시각.
    # 작업을 미리 알 수는 없지만 그때까지 기다리도록 하기 위함.
    max_time = max(timed_jobs.keys())
    # 현재 수행중인 작업의 잔여 작업시간.
    current_job_timer = 0
    # 현재 수행중인 작업이 요청된 시각. RTT 계산에 필요.
    current_job_requested_time = 0
    
    # 아직 진행중인 작업이 있거나: while current_job_timer > 0
    # 아직 뒤에 들어올 작업이 더 있다면: current_time <= max_time
    # 작업 수행을 종료하지 않고 계속 타이머 증가.
    while current_job_timer > 0 or current_time <= max_time:
    	# 현재 수행중인 작업 처리.
        current_job_timer -= 1
        # 만약 현재 작업이 끝났다면 RTT 목록에 추가.
        if current_job_timer == 0:
            return_times.append(current_time - current_job_requested_time)
        
        # 현재 시간대의 작업이 있다면 대기열에 추가.
        # 처리 시간(job)과 현재 시간(current_time) 튜플을 힙에 저장.
        if current_time in timed_jobs:
            for job in timed_jobs[current_time]:
                heapq.heappush(waiting_jobs, (job, current_time))
    
        # 현재 수행중인 작업이 끝났고 대기중인 작업이 있다면
        if current_job_timer < 1 and waiting_jobs:
            # 대기중인 작업을 꺼내서 현재 처리중인 작업으로 설정.
            required_time, requested_time = heapq.heappop(waiting_jobs)
            current_job_timer = required_time
            current_job_requested_time = requested_time
            
        current_time += 1
    
    # 만약 작업이 없는 경우 예외처리.
    if len(return_times) == 0:
        return 0
    else:
        return int(sum(return_times) / len(return_times))

후기

우선순위 큐를 활용하면 어렵지 않게 풀 수 있었지만 헷갈릴 수 있는 점이 많아 풀이를 구상하는 데 까다로웠던 것 같다.