[프로그래머스/42627번/JavaScript] 디스크 컨트롤러

문제

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를들어

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다.)

 

제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

 

입출력 예

jobs	return
[[0, 3], [1, 9], [2, 6]]	9
이 아래부터는 제가 임의로 추가한 테스트 케이스입니다.
[[0, 1], [10, 1]]	1
[[0, 1], [0, 2], [0, 3]]	3
[[10, 1], [0, 9]]	5
[[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1]]	5
[[0, 1000], [0, 2]]	502
[[0, 10], [2, 10], [9, 10], [15, 2]]	14
[[0, 10], [2, 12], [9, 19], [15, 17]]	25
[[0, 3], [1, 9], [2, 6]]	9
[[0, 1]]	1
[[1000, 1000]]	1000
[[0, 1], [0, 1], [0, 1]]	2
[[0, 1], [0, 1], [0, 1], [0, 1]]	2
[[0, 1], [1000, 1000]]	500
[[100, 100], [1000, 1000]]	550
[[10, 10], [30, 10], [50, 2], [51, 2]]	6
[[0, 3], [1, 9], [2, 6], [30, 3]]	7

---

풀이에 사용할 알고리즘 구상

이 문제에서 나온 하드디스크 컨트롤러는 다음 두 가지 특징을 가지고 있다.

1. 어떤 작업의 처리가 끝날 때까지 다른 작업의 처리는 일단 미뤄둔다.
   (중간에 다른 작업으로의 Context Switching이 발생하지 않는다.)
2. 작업을 요청한 프로세스들에 대해 소요시간이 가장 짧은 작업 요청부터 처리한다.

이 두 특징은 놀랍게도 운영체제의 CPU 스케줄링 알고리즘 중 비선점 스케줄링 방식인 SJF 방식과 동일한 특징을 가지고 있다. 운영체제의 CPU 스케줄링 알고리즘에 대해 자세히 알고 싶다면 여기를 클릭.

SJF 방식에 대해 알고 있다면, 실제로 SJF 방식에서 Priority Queue(정확히는 예상 소요 시간을 priority로 두는 Ready Queue)를 사용한다는 것을 알 것이다. 따라서 이 문제에선 Priority Queue를 사용하면 좋다.

그런데 안타깝게도 JavaScript는 C++이나 Java 같은 언어와 다르게, 구현되어 있는 Priority Queue가 없기 때문에 이를 직접 구현해야 한다. 나는 Queue에 입력이 발생할 때마다 배열을 Array.sort()하는 간접적인 방식으로 Priority Queue를 구현했다.

이제 어떤 알고리즘을 쓸 지 구상했으니 본격적으로 구현을 시작해보자.

먼저 jobs를 요청 시간에 따라 정렬하고, 현재 요청 상태인 작업을 담을 큐(waitQueue)를 선언한다. 다음으로 문제에서 요구하는 (종료시간-요청시간)을 계산해 담아둘 배열(timeList)도 만든다. 마지막으로, 현재 시간을 저장할 number 타입 변수 time을 선언한다.

위 준비과정이 끝났다면, waitQueue와 jobs 모두 빌 때까지 다음 과정을 반복한다.

1. 현재 시간 기준, 새로 요청을 한 작업이 있는지 찾아서 전부 waitQueue에 삽입한다.
2. 현재 시간 기준, 요청을 한 작업이 하나도 없을 경우 아직 요청하지 못한 작업이 있다는 뜻이기 때문에 해당 작업이 요청할 때까지 현재 시간을 늘리면서 기다린다.
3. 1번 과정에서 waitQueue에 입력이 발생했다면, waitQueue를 Array.sort()한다.
   (만약, JavaScript가 아닌 다른 언어였다면 그냥 waitQueue를 Priority Queue로 선언하면 이 과정을 생략할 수 있다.)
4. 3번 과정이 끝났다면, waitQueue가 빌 때까지 waitQueue에 들어있는 모든 작업들에 대해 (종료시간-요청시간)을 timeList에 담는다.

여기까지 왔다면 timeList에 우리가 구하고자 하는 모든 작업의 (종료시간-요청시간)이 저장된다. Array.reduce()를 적절히 사용해서 문제에서 요구하는 값을 반환하자.

 

제출 코드

function solution(jobs) {
    // 요청 시간에 따라 정렬
    jobs.sort((a, b) => a[0] - b[0]);
    let jobCount = jobs.length;
    // 요청 상태인 작업을 담을 큐
    let waitQueue = [];
    // 요청부터 종료까지 걸린 시간을 담을 배열
    let timeList = [];
    // 현재 시간
    let time = 0;
    while (waitQueue.length || jobs.length) {
        // 매 초마다 요청을 한 작업이 있는지 찾아서 전부 waitQueue에 삽입
        if (jobs.length) {
            while (time >= jobs[0][0]) {
                if (jobs.length) waitQueue.push(jobs.shift());
                if (!jobs.length) break;
            }
        }
        // 요청한 작업이 없을 경우, 아직 요청 전인 작업이 있다는 뜻이므로 시간만 늘림
        if (!waitQueue.length) {
            time++;
            continue;
        }
        // waitQueue를 최대한 빨리 끝나는 작업 순으로 재배치
        // js가 아니었다면, PriorityQueue를 써서 생략 가능
        waitQueue.sort((a, b) => a[1] - b[1]);
        // 모든 waitQueue의 작업들에 대해 (종료 시간 - 요청 시간)을 timeList에 담음
        if (waitQueue.length) {
            const [jobIndex, jobTime] = waitQueue.shift();
            time += jobTime;
            timeList.push(time - jobIndex);
        }
    }
    // timeList 배열을 reduce()하고 jobCount로 나눈 다음 소숫점 버림
    return Math.floor(timeList.reduce((pre, cur) => pre + cur) / jobCount);
}

 

회고

내가 포스팅했던 운영체제의 스케줄링 알고리즘과 관련된 문제여서 빠르게 풀 수 있었던 것 같다. 사실 운영체제의 스케줄링 알고리즘을 몰랐더라도 문제를 읽어보면 Priority Queue를 써야 한다는 것을 알 수 있었겠지만..