[programmers/python] 디스크 컨트롤러 - 힙(Heap)

- url : https://school.programmers.co.kr/learn/courses/30/lessons/42627

 

디스크 컨트롤러 문제는 우선순위 큐(Heap)를 활용한 전형적인 스케줄링 문제다.
각 작업은 요청 시각과 소요 시간을 가지고 있으며, 디스크는 한 번에 하나의 작업만 수행할 수 있다.

이 문제에서 디스크 컨트롤러는 다음과 같은 우선순위를 가진다:

1. 소요 시간이 짧은 작업이 우선
2. 소요 시간이 같다면 요청 시각이 빠른 작업이 우선
3. 둘 다 같다면 작업 번호가 낮은 작업이 우선

---

문제 요약

• jobs[i] = [요청 시각, 소요 시간]
• 각 작업의 반환 시간 = 완료 시각 - 요청 시각
• 모든 작업의 평균 반환 시간의 정수 부분을 구하는 것이 목표다.

---

예시

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

작업 처리 순서와 시간 흐름은 다음과 같다:

시각	상태
0	0번 요청 도착 → 작업 시작
1	1번 요청 도착 (대기 중)
3	0번 완료, 2번 도착
3	2번(5ms) vs 1번(9ms) → 2번 선택
8	2번 완료 → 1번 수행 시작
17	1번 완료

 

반환 시간:

• 0번: 3ms
• 1번: 17 - 1 = 16ms
• 2번: 8 - 3 = 5ms
  → 평균 = (3 + 16 + 5) / 3 = 8ms

---

구현 전략

• 현재 시각(t) 기준으로, 아직 요청되지 않은 작업은 무시하고, 요청된 작업들만 힙에 push한다.
• 힙에는 (소요시간, 요청시각, 작업번호) 순서로 저장한다.
• 작업이 없으면 시간을 1씩 증가시키며 다음 작업이 올 때까지 기다린다.

---

구현 코드

import heapq

def solution(jobs):
    t = 0                   # 현재 시각
    answer = 0              # 반환 시간 총합
    queue = []              # 대기 큐 (최소 힙)
    
    # 요청 시각 기준 정렬 (enumerate로 작업번호 포함)
    jobs_sorted = sorted(enumerate(jobs), key=lambda it: it[1][0])
    passed = [0] * len(jobs)  # 0: 미처리, 1: 큐에 등록됨, 2: 완료

    while passed.count(2) < len(jobs):
        for i, (s, l) in jobs_sorted:
            if passed[i] != 0:
                continue
            if s > t:
                break
            heapq.heappush(queue, (l, s, i))
            passed[i] = 1  # 큐에 추가 완료
        
        if queue:
            l, s, i = heapq.heappop(queue)
            t += l
            answer += (t - s)
            passed[i] = 2  # 처리 완료
        else:
            t += 1  # 작업 없을 경우 시간만 증가
    
    return answer // len(jobs)

• heapq는 (우선순위1, 우선순위2, ...) 형태의 튜플을 push하면 자동으로 순서가 정해진다.
• 요청된 작업만 대기큐에 넣어야 하므로, 현재 시각(t)보다 작거나 같은 작업만 push해야 한다.
• 작업 처리 후에는 t += 작업 시간, 반환 시간은 t - 요청 시각이다.

---

테스트 예시

print(solution([[0, 3], [1, 9], [3, 5]]))  # 출력: 8