디스크 컨트롤러 ⭐⭐

디스크 컨트롤러문제 보기

Level3

프로그래머스📅 2025-07-14

그리디스케줄링우선순위 큐

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 이 문제에서는 우선순위 디스크 컨트롤러라는 가상의 장치를 이용한다고 가정합니다. 우선순위 디스크 컨트롤러는 다음과 같이 동작합니다.

어떤 작업 요청이 들어왔을 때 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두는 대기 큐가 있습니다. 처음에 이 큐는 비어있습니다.
디스크 컨트롤러는 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면 가장 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 이때, 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높습니다.
하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행합니다.
하드디스크가 어떤 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면 하드디스크가 작업을 마치자마자 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 또, 하드디스크가 어떤 작업을 마치는 시점에 다른 작업이 들어오지 않더라도 그 작업을 마치자마자 또 다른 작업을 시작할 수 있습니다. 이 과정에서 걸리는 시간은 없다고 가정합니다.

예를 들어

0ms 시점에 3ms가 소요되는 0번 작업 요청
1ms 시점에 9ms가 소요되는 1번 작업 요청
3ms 시점에 5ms가 소요되는 2번 작업 요청

이 요청을 우선순위 디스크 컨트롤러가 처리하는 과정은 다음 표와 같습니다.

시점	하드디스크	대기 큐	디스크 컨트롤러
0ms	-	[ ]	-
0ms	-	[[0번, 0ms, 3ms]]	0번 작업 요청을 대기 큐에 저장
0ms	0번 작업 시작	[ ]	대기 큐에서 우선순위가 높은 0번 작업을 꺼내서 작업을 시킴
1ms	0번 작업 중	[[1번, 1ms, 9ms]]	1번 작업 요청을 대기 큐에 저장
3ms	0번 작업 완료	[[1번, 1ms, 9ms]]	-
3ms	-	[[1번, 1ms, 9ms], [2번, 3ms, 5ms]]	2번 작업 요청을 대기 큐에 저장
3ms	2번 작업 시작	[[1번, 1ms, 9ms]]	대기 큐에서 우선순위가 높은 2번 작업을 꺼내서 작업을 시킴
8ms	2번 작업 완료	[[1번, 1ms, 9ms]]	-
8ms	1번 작업 시작	[ ]	대기 큐에서 우선순위가 높은 1번 작업을 꺼내서 작업을 시킴
17ms	1번 작업 완료	[ ]	-

모든 요청 작업을 마쳤을 때 각 작업에 대한 반환 시간(turnaround time)은 작업 요청부터 종료까지 걸린 시간으로 정의합니다. 위의 우선순위 디스크 컨트롤러가 처리한 각 작업의 반환 시간은 다음 그림, 표와 같습니다.

우선순위 디스크 컨트롤러에서 모든 요청 작업의 반환 시간의 평균은 8ms(= (3ms + 16ms + 5ms) / 3)가 됩니다.

작업 번호	요청 시각	작업 종료 시각	반환 시간
0번	0ms	3ms	3ms (= 3ms - 0ms)
1번	1ms	17ms	16ms (= 17ms - 1ms)
2번	3ms	8ms	5ms (= 8ms - 3ms)

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 정수 배열 jobs가 매개변수로 주어질 때, 우선순위 디스크 컨트롤러가 이 작업을 처리했을 때 모든 요청 작업의 반환 시간의 평균의 정수부분을 return 하는 solution 함수를 작성해 주세요.

제한사항

1 ≤ jobs의 길이 ≤ 500
jobs[i]는 i번 작업에 대한 정보이고 [s, l] 형태입니다.
- s는 작업이 요청되는 시점이며 0 ≤ s ≤ 1,000입니다.
- l은 작업의 소요시간이며 1 ≤ l ≤ 1,000입니다.

입출력 예

입력

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

출력

설명

모든 요청 작업의 반환 시간의 평균은 8ms가 됩니다.

풀이 접근법

시간복잡도 : O(N log N)

공간복잡도 : O(N)

사용 알고리즘 :

그리디우선순위 큐정렬

핵심 포인트 :

SJF(Shortest Job First) 스케줄링을 우선순위 큐로 구현
시간 순으로 정렬된 작업 리스트를 순차 탐색
현재 시간까지 들어온 모든 요청을 우선순위 큐에 추가
처리할 작업이 없으면 다음 요청 시간으로 이동

경계값/반례 :

모든 작업이 0초에 시작하는 경우: 순수 SJF 스케줄링
작업 간 긴 간격이 있는 경우: 시간 이동 필요
동시에 여러 작업이 들어오는 경우: 우선순위 큐에서 최적 선택

핵심 아이디어

SJF(Shortest Job First) 스케줄링을 우선순위 큐로 구현
현재 시간까지 들어온 모든 요청을 우선순위 큐에 추가하고 최적의 작업 선택
처리할 작업이 없으면 다음 요청 시간으로 시간 이동
index 변수로 중복 삽입 방지

해결 방법

작업을 요청시간 순으로 정렬
우선순위 큐 설정 (소요시간 → 요청시각 → 번호 순)
메인 루프에서 현재시간까지의 요청들을 큐에 추가
큐에서 최적 작업 선택하여 처리, 반환시간 계산
큐가 비어있으면 다음 요청시간으로 시간 이동

내부 해부 과정

예시 1 : [[0, 3], [1, 9], [3, 5]]

초기 설정

끝나는 시간을 체크 타임(currentTime)으로 설정한다. currentTime = 0 부터 시작한다.

1. 첫 번째 작업 처리 (0초)

[0, 3]가 들어온다. 하드 디스크는 비어 있다. [0, 3] 작업 수행
- start = 0 (실제 요청 시간)
- end = currentTime + length = 0 + 3 = 3 (실제 마감 시간)
- currentTime = end = 3
- 반환시간 = end - start = 3

2. 작업 중 들어오는 요청들

1초에 [1, 9]가 들어온다. currentTime = 3 ≥ 1 이므로 하드 디스크는 사용 중이다. [1, 9]를 대기 큐에 전달
3초에 [3, 5]가 들어온다. currentTime = 3 ≥ 3 이므로 하드 디스크는 사용 중이다. [3, 5]를 대기 큐에 전달

3. 두 번째 작업 처리 (3초)

3초로 1번 작업 종료. 우선 순위가 높은 3번 작업 [3, 5]를 꺼낸다. [3, 5] 작업 수행
- start = 3 (실제 요청 시간)
- end = currentTime + length = 3 + 5 = 8 (실제 마감 시간)
- currentTime = end = 8
- 반환시간 = end - start = 5

4. 세 번째 작업 처리 (8초)

8초로 3번 작업 종료. 8초에서 마지막인 [1, 9]를 꺼낸다. [1, 9] 작업 수행
- start = 1 (실제 요청 시간)
- end = currentTime + length = 8 + 9 = 17 (실제 마감 시간)
- currentTime = end = 17
- 반환시간 = end - start = 16

예시 2 : [[1, 4], [7, 9], [1000, 3]]

초기 설정

끝나는 시간을 체크 타임(currentTime)으로 설정한다. currentTime = 0 부터 시작한다.

1. 대기 상태 (0초)

현재 시간은 0초지만 들어오는 요청은 없고, 대기 중인 요청도 없다.
시간 이동: 다음 요청 시간인 1초로 이동

2. 첫 번째 작업 처리 (1초)

1초에 [1, 4]가 들어온다. 하드 디스크는 비어 있다. [1, 4] 작업 수행
- start = 1 (실제 요청 시간)
- end = currentTime + length = 1 + 4 = 5 (실제 마감 시간)
- currentTime = end = 5
- 반환시간 = end - start = 4

3. 대기 상태 (5초)

현재 시간은 5초지만 들어오는 요청은 없고, 대기 중인 요청도 없다.
시간 이동: 다음 요청 시간인 7초로 이동

4. 두 번째 작업 처리 (7초)

7초에 [7, 9]가 들어온다. 하드 디스크는 비어 있다. [7, 9] 작업 수행
- start = 7 (실제 요청 시간)
- end = currentTime + length = 7 + 9 = 16 (실제 마감 시간)
- currentTime = end = 16
- 반환시간 = end - start = 9

5. 대기 상태 (16초)

현재 시간은 16초지만 들어오는 요청은 없고, 대기 중인 요청도 없다.
시간 이동: 다음 요청 시간인 1000초로 이동

6. 세 번째 작업 처리 (1000초)

1000초에 [1000, 3]가 들어온다. 하드 디스크는 비어 있다. [1000, 3] 작업 수행
- start = 1000 (실제 요청 시간)
- end = currentTime + length = 1000 + 3 = 1003 (실제 마감 시간)
- currentTime = end = 1003
- 반환시간 = end - start = 3

해부 과정으로부터 알게된 핵심 포인트들

1. 동시 요청 처리의 필요성
- [[0, 3], [1, 9], [3, 5]]의 경우 첫 번째 작업이 끝나는 3초 시점에 이미 1초와 3초에 들어온 요청들이 대기하고 있다.
- ⇒ 동시에 들어오는 요청들이 생길 수 있다는 것을 알 수 있다.
- 결론: 현재 시간(currentTime) 이하의 작업들을 대기큐에 넣고 우선순위 순서로 꺼내야 한다.
2. 시간 이동의 필요성
- [[1, 4], [7, 9], [1000, 3]]에서 초반 대기 시간과 작업 간 대기 시간이 발생하는 경우가 있다.
- 작업을 처리해야만 시간이 이동되는 경우 ⇒ 대기 시간이 존재하게 되면 작업이 아예 멈춘다.
- 결론: 시간을 다음 요청의 시작 시간으로 이동시켜야 한다.
3. 작업 처리 방식
- 작업이 들어오면 고려해야 하는 것은 요청의 시작 시간이 현재 시간보다 작거나 같은지
  - 작거나 같다면, 대기 큐에 넣어야 한다.
  - 크다면, 해당 시작 시간으로 현재 시간을 이동해야 한다.
- 위의 작업이 끝나면 하나를 꺼내서 작업한다.
- 결론: 모든 요청은 대기큐를 거쳐서 처리되어야 하며, 현재 시간에 따라 요청을 큐에 넣거나 시간을 이동시키는 방식으로 처리해야 한다.

생각 과정

종합 예시: [[1, 6], [3, 9], [4, 10], [15, 3]]

끝나는 시간을 체크 타임(currentTime)으로 설정한다. currentTime = 0 부터 시작한다.
우선순위 큐에 넣은 항목을 알기 위해 index를 설정한다. (초기값 index = 0)
- 단, 우선순위 큐에 넣기 전에 먼저 시작 시간 순서로 정렬을 해야지 index로 관리할 수 있다.
0초 이하의 작업들을 모두 대기 큐에 넣는다.
- 없음
- 대기 큐도 비어있음 ⇒ 1초로 시간 이동 (currentTime = 1)
1초 이하의 작업들을 모두 대기 큐에 넣는다. (currentTime = 1)
- [1, 6] 삽입 (index = 1)
우선 순위에 따라 꺼낸다.
- [1, 6] 제거
- start = 1 (실제 요청 시간)
- end = currentTime + length = 1 + 6 = 7
- currentTime = end = 7
- 반환시간 = end - start = 7 - 1 = 6
- 완료 항목 : 1개
7초 이하의 작업들을 모두 대기 큐에 넣는다. (currentTime = 7)
- [3, 9] 삽입 (index = 2)
- [4, 10] 삽입 (index = 3)
우선 순위에 따라 꺼낸다.
- [3, 9] 제거 (소요시간 9 < 10이므로 우선순위 높음)
- start = 3 (실제 요청 시간)
- end = currentTime + length = 7 + 9 = 16
- currentTime = end = 16
- 반환시간 = end - start = 16 - 3 = 13
- 완료 항목 : 2개
16초 이하의 작업들을 모두 대기 큐에 넣는다. (currentTime = 16)
- [15, 3] 삽입 (index = 4)
우선 순위에 따라 꺼낸다.
- [15, 3] 제거 (소요시간 3 < 10이므로 우선순위 높음)
- start = 15 (실제 요청 시간)
- end = currentTime + length = 16 + 3 = 19
- currentTime = end = 19
- 반환시간 = end - start = 19 - 15 = 4
- 완료 항목 : 3개
19초 이하의 작업들을 모두 대기 큐에 넣는다. (currentTime = 19)
- 없음 ⇒ 모두 삽입했음 (index = jobs.length)
- 대기 큐에 [4, 10] 존재
마지막으로 [4, 10] 제거
- start = 4 (실제 요청 시간)
- end = currentTime + length = 19 + 10 = 29
- currentTime = end = 29
- 반환시간 = end - start = 29 - 4 = 25
- 완료 항목 : 4개
평균 반환시간: (6 + 13 + 4 + 25) / 4 = 12

핵심 패턴

1️⃣ 우선순위 큐의 정렬 기준

PriorityQueue<Job> pq = new PriorityQueue<>((a, b) -> {
  if (a.length != b.length) return Integer.compare(a.length, b.length);
  if (a.start != b.start) return Integer.compare(a.start, b.start);
  return Integer.compare(a.id, b.id);
});

SJF 스케줄링을 구현하기 위해 소요시간을 첫 번째 기준으로 설정
걸리는 시간이 같을 경우 요청 시간, 그다음 작업 번호 순으로 우선순위 결정

2️⃣ 중복 삽입 방지를 위한 index 관리

while (index < list.size() && list.get(index).start <= currentTime) {
  pq.add(list.get(index));
  index++;
}

시간순으로 정렬된 작업 리스트를 순차적으로 탐색
index 변수로 이미 검토한 작업들을 추적하여 중복 삽입 방지
이외에 완료 항목을 체크하기 위한 count 변수 관리

3️⃣ 유휴 시간 처리

if (!pq.isEmpty()) {
  // 작업 처리
} else {
  if (index < list.size()) {
    currentTime = list.get(index).start;
  }
}

대기큐가 비어있을 때 다음 작업의 요청시간으로 시간 이동
하드디스크가 놀고 있는 시간을 효율적으로 건너뛰기

최종 제출 코드

import java.util.*;

class Solution {
  static class Job {
    int id;
    int start;
    int length;

    public Job(int id, int start, int length) {
      this.id = id;
      this.start = start;
      this.length = length;
    }
  }

  public int solution(int[][] jobs) {
    List<Job> list = new ArrayList<>();
    for (int i = 0; i < jobs.length; i++) {
      list.add(new Job(i, jobs[i][0], jobs[i][1]));
    }

    list.sort((a, b) -> Integer.compare(a.start, b.start));

    PriorityQueue<Job> pq = new PriorityQueue<>((a, b) -> {
      if (a.length != b.length) return Integer.compare(a.length, b.length);
      if (a.start != b.start) return Integer.compare(a.start, b.start);
      return Integer.compare(a.id, b.id);
    });

    int count = 0;
    int sum = 0;
    int currentTime = 0;
    int index = 0;
    
    while (count < jobs.length) {
      while (index < list.size() && list.get(index).start <= currentTime) {
        pq.add(list.get(index));
        index++;
      }

      if (!pq.isEmpty()) {
        Job job = pq.poll();
        int start = job.start;
        int end = currentTime + job.length;
        currentTime = end;
        sum += end - start;
        count++;
      } else {
        if (index < list.size()) {
          currentTime = list.get(index).start;
        }
      }
    }

    return sum / jobs.length;
  }
}