[알고리즘] 디스크 컨트롤러 / JavaScript / 프로그래머스 Lv.3

📖 문제

문제 풀러 가기

문제 설명

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

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

예를 들어

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

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 다음과 같습니다.

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

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

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

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

제한 사항

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

입출력 예

🧮 우선순위 큐 구현

각 작업은 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순의 우선순위를 가지고 있습니다. 대기 큐에 작업을 추가하거나, 대기 큐에서 작업을 꺼낼 때 대기 큐 내의 작업들을 우선순위에 따라 정렬하면서 $O(log N)$의 시간 복잡도를 가지도록 합니다.

우선순위 큐에 대한 자세한 내용은 나중에 따로 다루도록 하고, 이번 포스트에서는 제가 구현한 우선순위 큐의 주요 메서드에 대해서만 살펴보겠습니다.

1️⃣ 두 작업의 우선순위를 비교하는 compare 메서드

대기 큐에 새로운 작업을 추가하거나, 작업을 제거하는 과정에서 우선순위 비교가 필요합니다. 문제의 요구사항에 따라 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 비교하는 compare 메서드입니다. task1이 task2보다 우선순위가 높은 경우 true를, 그렇지 않은 경우 false를 반환합니다.

compare(task1, task2) {
    // 1. 작업의 소요시간이 짧은 것
    if (task1[2] !== task2[2]) return task1[2] < task2[2];
    // 2. 작업의 요청 시각이 빠른 것
    else if (task1[1] !== task2[1]) return task1[1] < task2[1];
  	// 3. 작업의 번호가 작은 것
    else return task1[0] < task2[0];
}

2️⃣ 우선순위 큐에 작업을 추가하는 insert 메서드

대기 큐에 새로운 작업을 추가하기 위해 큐의 맨 마지막 위치에 원소를 추가합니다(push). 하지만 현재 설계하고 있는 것은 우선순위 큐이기 때문에, 우선순위가 가장 높은 원소가 큐의 가장 앞에 오도록 해야 합니다. 이를 위해 새로운 원소와 부모 노드의 우선순위를 비교하여 우선순위가 더 높다면 두 원소를 바꾸는 과정이 필요합니다.

insert(task) {
    this.heap.push(task);
    this.bubbleUp();
}

bubbleUp() {
    let index = this.heap.length - 1;

    while (index > 0) {
      let parentIndex = parseInt((index - 1) / 2);

      if (this.compare(this.heap[index], this.heap[parentIndex])) {
          this.swap(index, parentIndex);
          index = parentIndex;
      } else break;
    }
}

3️⃣ 우선순위 큐에서 작업을 제거하는 delete 메서드

다음으로 대기 큐에서 작업을 제거합니다. 우선순위 큐에서는 원소를 제거할 때 우선순위가 가장 높은 루트 노드를 제거한 후, 가장 마지막 노드를 루트 노드로 옮기고, 우선순위가 가장 높은 원소가 루트 노드에 위치하도록 정렬하는 과정이 필요합니다.

delete() {
    if (this.isEmpty()) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const rootNode = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();

    return rootNode;
}

bubbleDown() {
    let index = 0;

    while (true) {
        let leftIndex = index * 2 + 1;
        let rightIndex = index * 2 + 2;
        let smallestIndex = index;

        if (
            this.heap[leftIndex] &&
            this.compare(this.heap[leftIndex], this.heap[smallestIndex])
        ) {
          	smallestIndex = leftIndex;
        }

        if (
            this.heap[rightIndex] &&
            this.compare(this.heap[rightIndex], this.heap[smallestIndex])
        ) {
          	smallestIndex = rightIndex;
        }

        if (smallestIndex === index) break;
        else {
            this.swap(index, smallestIndex);
            index = smallestIndex;
        }
    }
}

🌕 전체 코드

우선순위 큐 클래스의 전체 코드는 다음과 같습니다.

class PriorityQueue {
	constructor() {
		this.heap = [];
	}

	isEmpty() {
		return this.heap.length === 0;
	}

	swap(idx1, idx2) {
		[this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
	}

	compare(task1, task2) {
		// 1. 작업의 소요시간이 짧은 것
		if (task1[2] !== task2[2]) return task1[2] < task2[2];
		// 2. 작업의 요청 시각이 빠른 것
        else if (task1[1] !== task2[1]) return task1[1] < task2[1];
		else return task1[0] < task2[0];
	}

	insert(task) {
		this.heap.push(task);
		this.bubbleUp();
	}

	bubbleUp() {
		let index = this.heap.length - 1;

		while (index > 0) {
			let parentIndex = parseInt((index - 1) / 2);

			if (this.compare(this.heap[index], this.heap[parentIndex])) {
				this.swap(index, parentIndex);
				index = parentIndex;
			} else break;
		}
	}
  
    delete() {
        if (this.isEmpty()) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const rootNode = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();

        return rootNode;
    }

	bubbleDown() {
		let index = 0;

		while (true) {
			let leftIndex = index * 2 + 1;
			let rightIndex = index * 2 + 2;
			let smallestIndex = index;

			if (
				this.heap[leftIndex] &&
				this.compare(this.heap[leftIndex], this.heap[smallestIndex])
			) {
				smallestIndex = leftIndex;
			}

			if (
				this.heap[rightIndex] &&
				this.compare(this.heap[rightIndex], this.heap[smallestIndex])
			) {
				smallestIndex = rightIndex;
			}

			if (smallestIndex === index) break;
			else {
				this.swap(index, smallestIndex);
				index = smallestIndex;
			}
		}
	}
}

🧮 풀이 1

다음으로 위에서 설계한 우선순위 큐를 사용해 모든 요청 작업의 반환 시간의 평균의 정수부분을 return 하는 solution 함수를 작성해보겠습니다. 이 문제의 핵심은 시간의 흐름에 따라 그 시간에 도착한 작업들을 대기 큐에 넣고, 하드디스크가 비어 있다면 우선순위가 가장 높은 작업을 꺼내 처리하는 것입니다.

함수의 로직을 단계별로 살펴보면 다음과 같습니다.

1️⃣ jobs 배열을 요청시각 기준으로 정렬

입력으로 주어지는 jobs 배열은 [작업이 요청되는 시점, 작업의 소요시간] 형태로, 작업 번호는 배열의 인덱스로 주어지기 때문에 map을 활용해 jobs 배열을 [작업 번호, 작업이 요청되는 시점, 작업의 소요시간] 형태로 바꿔줍니다.

또한 시간의 흐름에 따라 작업을 처리해야 하므로, jobs 배열을 요청 시각을 기준으로 정렬합니다.

jobs = jobs.map((job, i) => [i, ...job]).sort((a, b) => a[1] - b[1]);

2️⃣ 시간에 따라 작업을 대기 큐에 추가

반복문을 돌면서 현재 시각을 나타내는 time 변수가 1ms 마다 1씩 증가하고 있습니다. time이 $n$ms가 되었을 때, jobs에 $n$ms에 요청한 작업이 들어 있다면, 모두 대기 큐에 추가합니다.

while (jobs.length) {
    if (jobs[0][0] === time) waitingQueue.insert(jobs.shift());
    else break;
}

3️⃣ 하드디스크에 진행 중인 작업이 없다면 작업 수행

하드디스크가 작업을 하고 있지 않고(disk === 0) 대기 큐에서 대기하는 작업이 있는 경우(!waitingQueue.isEmpty()), 하드디스크는 작업을 시작합니다.

하드디스크의 남은 작업 시간을 나타내는 disk 변수를 작업 소요 시간으로 변경하고, 작업 요청부터 종료까지 걸린 시간을 계산하여 전체 작업의 반환 시간에 더해줍니다.

시간이 지남에 따라(반복문을 돌 때 마다) 현재 시각을 나타내는 time 변수는 1씩 증가시키고, disk 변수는 1씩 감소시키며 시뮬레이션 합니다.

if (disk === 0 && !waitingQueue.isEmpty()) {
    const [index, reqTime, operTime] = waitingQueue.delete();
    disk = operTime;
    totalTime += time + operTime - reqTime;
}

🌕 전체 코드

위 과정을 모두 포함한 전체 풀이는 다음과 같습니다.

function solution(jobs) {
	jobs = jobs.map((job, i) => [i, ...job]).sort((a, b) => a[1] - b[1]);

	let waitingQueue = new PriorityQueue();
	let totalTime = 0;
	let jobsCnt = jobs.length;
	let time = 0;
	let disk = 0;

	while (jobs.length || !waitingQueue.isEmpty()) {
		while (jobs.length) {
			if (jobs[0][1] === time) waitingQueue.insert(jobs.shift());
			else break;
		}

		if (disk === 0 && !waitingQueue.isEmpty()) {
			const [index, reqTime, operTime] = waitingQueue.delete();
			disk = operTime;
			totalTime += time + operTime - reqTime;
		}

		time++;
		disk--;
	}

	return parseInt(totalTime / jobsCnt);
}

🧪 실행결과

하지만 이 코드를 실행했을 때, 이번에도 시간 초과를 마주하게 되었습니다.

⚠️ 문제 원인 분석

어떤 부분에서 연산 횟수가 증가하여 시간 초과가 되었을까요? 원인을 알아보기 위해 다시 한 번 제한사항을 살펴보겠습니다.

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

1️⃣ 첫 번째 과정에서 배열의 map을 위해 $O(n)$,sort을 위해 $O(nlogn)$이 소요되어 총 $O(nlogn)$의 연산이 필요합니다.

이어서 가장 바깥쪽 반복문을 살펴보겠습니다. time을 1씩 증가시키며 전체 시간을 전부 순회하는 시뮬레이션 과정에서 작업의 수 * 작업의 요청 시각에 따라 최악의 경우 $O(T)=O(500,000)$의 연산이 필요합니다.

2️⃣ 두 번째 과정에서 배열의 가장 첫 번째 원소를 꺼내고 모든 원소를 한 칸씩 앞으로 당기는 shift를 위해 $O(n)$이 소요되며 배열의 길이만큼 shift 연산이 필요하므로 $O(n^2)$의 연산이 필요합니다. 대기 큐에 꺼낸 원소를 추가하는 연산은 $O(nlogn)$번 소요되므로 최종적으로 $O(n^2)$의 연산이 필요합니다.

3️⃣ 세 번째 과정에서 우선순위 큐에서 n개의 원소를 제거하기 위해 총 $O(nlogn)의 연산이 필요합니다.

위 풀이의 전체 시간 복잡도는 $O(n^2 + T)=O(750,000)$ 입니다. 이처럼 1ms 마다 time 변수를 증가시키는 방법으로 코드를 제출하면 시간 초과가 발생하게 될 것입니다.

🧮 풀이 2

따라서 1ms 마다 time 변수를 증가시키는 것이 아니라, 하드디스크가 비어 있을 때는 다음 수행할 작업의 요청 시간으로 time 변수를 바로 이동시킴으로써 복잡도를 개선할 수 있습니다.

⚒️ 메인 while 문 반복 횟수 개선

기존에 1ms에 한 번씩 time 변수를 증가시키고 disk 변수를 감소시켰다면, 이제 하드디스크에서 작업이 수행 중일 때만 이 로직을 따르고 그렇지 않은 경우 다음으로 수행할 작업의 요청 시간으로 바로 이동하도록 합니다. 이렇게 하면 전체 시간을 전부 순회하는 시뮬레이션 과정이 불필요하게 되어 연산 횟수를 크게 단축할 수 있습니다.

// 3-1. 하드디스크에서 작업을 수행 중이라면 1ms 마다 time, 남은 작업 시간 업데이트
if (disk > 0) {
    disk--;
    time++;
}
// 3-2. 하드디스크에서 수행 중인 작업이 없다면 다음으로 수행할 작업의 요청 시간으로 바로 이동
else {
  	if (jobs.length) time = jobs[0][1];
}

🌕 전체 코드

수정된 전체 코드는 다음과 같습니다.

function solution(jobs) {
    // 0. 작업들을 요청 시각 기준으로 정렬
	jobs = jobs.map((job, i) => [i, ...job]).sort((a, b) => a[1] - b[1]);

	let waitingQueue = new PriorityQueue();
	let totalTime = 0;
	let jobsCnt = jobs.length;
	let time = 0;
	let disk = 0;
    
    // 작업이 대기 큐에 들어가지 않았거나, 대기 큐에 남은 작업이 있다면 반복
	while (jobs.length || !waitingQueue.isEmpty()) {
        // 1. 해당 time에 작업 요청이 들어오면 대기 큐에 [작업의 번호, 작업의 요청 시각, 작업의 소요 시간] 저장
		while (jobs.length) {
            // 1-1. 대기 큐에 작업을 추가하면 우선순위에 따라 정렬
			if (jobs[0][1] === time) waitingQueue.insert(jobs.shift());
			else break;
		}
        
        // 2. 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면 가장 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업 수행
		if (disk === 0 && !waitingQueue.isEmpty()) {
            // 2-1. 우선순위가 높은 작업을 대기 큐에서 꺼내고 우선순위에 따라 정렬
			const [index, reqTime, operTime] = waitingQueue.delete();
            // 2-2. 하드디스크의 남은 작업 시간 업데이트
			disk = operTime;
            // 2-3. 각 작업에 대한 반환 시간(작업 요청부터 종료까지 걸린 시간) 계산
			totalTime += time + operTime - reqTime;
		}
        
        // 3-1. 하드디스크에서 작업을 수행 중이라면 1ms 마다 time, 남은 작업 시간 업데이트
		if (disk > 0) {
            disk--;
            time++;
        }
        // 3-2. 하드디스크에서 수행 중인 작업이 없다면 다음으로 수행할 작업의 요청 시간으로 바로 이동
        else {
            if (jobs.length) time = jobs[0][1];
        }
	}

	return parseInt(totalTime / jobsCnt);
}

🧪 실행결과

최종적으로 시간 복잡도 역시 $O(n^2 + T)=O(750,000)$에서 $O(n^2)=O(250,000)$으로 최악의 경우 50만 번의 연산이 줄어었고, 코드 제출 시에도 문제 없이 모든 테스트 케이스를 통과하는 것을 확인할 수 있게 됩니다.