프로그래머스 디스크 컨트롤러 풀이: 대기 작업 최소 힙 스케줄링

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

• 문제: 디스크 컨트롤러
• 출처: 프로그래머스 코딩테스트 연습, 힙(Heap)
• 자체 판단 난이도: Level 3

작업이 요청된 시점과 현재 대기 중인 작업을 분리해 관리해야 하며, 대기 중인 작업 중 소요 시간이 가장 짧은 작업을 반복해서 선택해야 한다. 시간 흐름을 시뮬레이션하면서 힙의 입력 시점과 평균 반환 시간을 함께 관리해야 하므로 Level 3으로 판단했다.

1. 문제 요약

하드디스크는 한 번에 하나의 작업만 처리한다. 작업은 [요청 시각, 소요 시간]으로 주어지고, 디스크가 비어 있을 때 대기 중인 작업이 있다면 다음 우선순위로 작업을 선택한다.

1. 소요 시간이 짧은 작업
2. 요청 시각이 이른 작업
3. 작업 번호가 작은 작업

작업이 요청된 시각부터 종료될 때까지의 시간을 반환 시간이라고 한다. 모든 작업을 처리한 뒤 반환 시간 평균의 정수 부분을 반환해야 한다.

작업 수는 최대 500개이고, 요청 시각과 소요 시간은 각각 최대 1,000이다.

예를 들어 [[0, 3], [1, 9], [3, 5]]에서는 0번 작업을 먼저 처리하고, 3ms 시점에 대기 중인 1번과 새로 요청된 2번 중 소요 시간이 짧은 2번을 처리한다. 반환 시간은 3, 16, 5이고 평균의 정수 부분은 8이다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

상태 전이와 경계 처리

작업을 두 부분으로 나누어 관리한다.

• 아직 현재 시각에 도착하지 않은 작업: 요청 시각 오름차순 목록
• 현재 시각까지 요청되어 대기 중인 작업: 최소 힙

최소 힙에는 (소요 시간, 요청 시각, 작업 번호)를 저장한다. Python 튜플 비교 규칙에 따라 소요 시간이 짧은 작업이 먼저 나오고, 소요 시간이 같으면 요청 시각, 작업 번호 순으로 우선순위가 적용된다.

시뮬레이션의 한 단계는 다음과 같다.

1. 현재 시각까지 요청된 모든 작업을 대기 힙에 넣는다.
2. 대기 힙이 비어 있으면 아직 요청되지 않은 다음 작업의 요청 시각으로 현재 시각을 이동한다.
3. 다시 현재 시각까지 요청된 작업을 힙에 넣는다.
4. 힙에서 우선순위가 가장 높은 작업을 꺼내 처리한다.
5. 종료 시각에서 요청 시각을 뺀 반환 시간을 누적한다.

코드에서는 먼저 대기 힙이 비었을 때 시간을 다음 요청 시각으로 이동한 후, 현재 시각까지의 작업을 넣는 방식으로 구현한다. 대기 중인 작업이 있으면 디스크가 쉬지 않고 바로 다음 작업을 시작하므로 시간을 한 칸씩 증가시키지 않는다.

대기 작업은 남은 처리 시간 순으로 고르는 이유

현재 대기 중인 작업들의 요청 시각은 이미 지나갔으므로, 이 작업들의 대기 시간은 어떤 순서로 처리하더라도 현재 시점까지 이미 결정되어 있다. 이제 두 작업 A, B 중 하나를 먼저 처리한다고 할 때, 소요 시간이 짧은 작업을 먼저 처리하면 두 작업의 종료 시간 합이 작아진다.

소요 시간이 a <= b인 두 작업을 비교하면 다음과 같다.

A -> B: 2a + b
B -> A: a + 2b

따라서 대기 중인 작업 중 소요 시간이 가장 짧은 작업부터 처리하는 것이 평균 반환 시간을 줄이는 선택이다. 소요 시간이 같으면 요청 시각과 작업 번호를 기준으로 정해진 우선순위를 그대로 적용한다.

그리디 선택이 최적인 이유

현재 대기 중인 작업 순서에서 소요 시간이 긴 작업 B가 짧은 작업 A보다 앞에 있다고 하자. 두 작업을 서로 바꾸면 다른 작업의 처리 순서는 그대로인 상태에서 두 작업의 반환 시간 합이 줄거나 같아진다.

A 먼저: 2 * duration(A) + duration(B)
B 먼저: duration(A) + 2 * duration(B)

duration(A) <= duration(B)이면 A를 먼저 처리하는 쪽이 유리하다. 이런 인접한 역순을 반복해서 바꾸면 대기 중 작업은 소요 시간 오름차순이 되고, 매 작업이 끝날 때마다 새로 들어온 작업을 포함해 같은 판단을 적용할 수 있다.

오답 접근과 반례

요청 시각이 빠른 순서로만 작업을 처리하면 대기 시간이 긴 작업이 먼저 처리되지만 평균 반환 시간이 최소가 되지는 않는다.

jobs = [[0, 3], [1, 9], [3, 5]]

0번 작업이 끝나는 3ms 시점에는 1번과 2번이 모두 대기 중이다. 요청 시각 순서대로 1번을 먼저 처리하면 1번 종료는 12ms, 2번 종료는 17ms가 된다. 소요 시간 순서로 2번을 먼저 처리하면 2번은 8ms에 끝나고 1번은 17ms에 끝나 전체 반환 시간 합이 더 작아진다.

대기 중인 작업이 없는데 현재 시각을 1씩 증가시키면 결과는 얻을 수 있어도 불필요한 반복이 생긴다. 다음 요청 시각으로 바로 이동해야 요청 간 간격을 효율적으로 처리할 수 있다.

시간·공간 복잡도

작업을 요청 시각으로 정렬하는 데 O(n log n) 시간이 필요하다. 각 작업은 힙에 한 번 들어가고 한 번 나오므로 힙 처리에도 O(n log n) 시간이 필요하다. 전체 시간 복잡도는 O(n log n)다.

정렬된 작업 목록과 대기 힙을 저장하므로 공간 복잡도는 O(n)다.

3. 문제 해결 코드 (Python)

import heapq


def solution(jobs):
    ordered_jobs = sorted(
        (request_time, duration, job_id)
        for job_id, (request_time, duration) in enumerate(jobs)
    )

    waiting = []
    current_time = 0
    job_index = 0
    total_turnaround = 0

    while job_index < len(ordered_jobs) or waiting:
        if not waiting and current_time < ordered_jobs[job_index][0]:
            current_time = ordered_jobs[job_index][0]

        while job_index < len(ordered_jobs):
            request_time, duration, job_id = ordered_jobs[job_index]
            if request_time > current_time:
                break

            heapq.heappush(waiting, (duration, request_time, job_id))
            job_index += 1

        duration, request_time, _ = heapq.heappop(waiting)
        current_time += duration
        total_turnaround += current_time - request_time

    return total_turnaround // len(jobs)

ordered_jobs는 요청 시각 순서로 다음에 들어올 작업을 빠르게 찾기 위한 목록이다. 대기 힙의 우선순위는 문제의 조건과 같은 (소요 시간, 요청 시각, 작업 번호) 순서다.

작업을 처리한 뒤 current_time - request_time을 더하면 대기 시간과 실제 처리 시간이 함께 포함된 반환 시간이 된다. 마지막에 작업 수로 나눈 몫만 반환해 평균의 정수 부분을 구한다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 대기 작업 선택과 유휴 시간 처리를 확인할 수 있다.

assert solution([[0, 3], [1, 9], [3, 5]]) == 8
assert solution([[5, 2]]) == 2
assert solution([[0, 10], [0, 1], [0, 2]]) == 5

4. 공식 예제와 추가 검증

공식 예제와 동일 시각 요청, 작업 사이의 유휴 시간, 우선순위 동률을 Python 코드로 실행했다.

공식 예제

입력: jobs = [[0, 3], [1, 9], [3, 5]]
기대 출력: 8
확인 결과: 통과
검증 목적: 작업 종료 시점에 새로 요청된 작업까지 대기 큐에 넣고 선택하는지 확인

추가 검증 1: 모든 작업이 동시에 요청된 경우

입력: jobs = [[0, 10], [0, 1], [0, 2]]
기대 출력: 5
확인 결과: 통과
검증 목적: 소요 시간이 짧은 순서로 처리해 반환 시간 평균을 줄이는지 확인

추가 검증 2: 첫 요청이 늦은 경우

입력: jobs = [[5, 2]]
기대 출력: 2
확인 결과: 통과
검증 목적: 대기 힙이 비었을 때 다음 요청 시각으로 바로 이동하는지 확인

추가 검증 3: 작업 사이에 유휴 시간이 있는 경우

입력: jobs = [[0, 3], [100, 2], [101, 1]]
기대 출력: 2
확인 결과: 통과
검증 목적: 현재 작업이 끝난 뒤 미래 요청 시각까지 이동하고, 이후 대기 작업의 우선순위를 적용하는지 확인

추가 검증 4: 소요 시간이 같을 때의 우선순위

입력: jobs = [[0, 5], [0, 5], [0, 1]]
기대 출력: 6
확인 결과: 통과
검증 목적: 짧은 작업을 먼저 처리하고 같은 소요 시간은 요청 시각과 작업 번호 순으로 관리하는지 확인

5. 다른 풀이 방식 검색 및 비교

• 프로그래머스 공식 문제는 요청 시각, 소요 시간, 반환 시간과 대기 작업의 우선순위를 정의한다.
• Teferi의 디스크 컨트롤러 풀이는 요청 시각 순으로 작업을 준비하고 대기 중인 작업을 최소 힙으로 선택하는 스케줄링 접근을 설명한다.

요청 시각 순서대로만 처리하는 FIFO 방식은 구현이 쉽지만 평균 반환 시간이 커질 수 있다. 현재 대기 중인 작업을 최소 힙으로 관리하면 소요 시간이 짧은 작업을 바로 꺼낼 수 있다. 이 글에서는 힙 원소에 요청 시각과 작업 번호까지 함께 저장해 문제의 동률 우선순위도 명시적으로 반영했다.

마무리

디스크 컨트롤러는 시간 흐름과 대기 작업의 우선순위를 함께 시뮬레이션하는 힙 문제다. 현재 시각까지 도착한 작업을 모두 대기 힙에 넣고, 그중 소요 시간이 가장 짧은 작업을 처리하면 평균 반환 시간을 최소화할 수 있다. 대기 작업이 없을 때는 다음 요청 시각으로 시간을 바로 이동하는 것이 구현의 중요한 경계 처리다.