[프로그래머스] 디스크 컨트롤러 - JavaScript

문제 출처

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

프로그래머스

문제 설명

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

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입니다.

---

입출력 예

입출력 예 설명

입출력 예 #1

• 문제에 주어진 예와 같습니다.

풀이 방법

• 정렬과 timer 계산만 잘 하면 되는 문제였다

1. jobs에는 작업들이 들어가있지만, 이게 정렬이 되어있단 보장이 없으므로 먼저 작업 순서(0초 -> 1초 -> 2초....)로 정렬하여 배열을 재구성한다.
2. taskQueue에 작업을 옮겨담아 작업을 수행하고, 이 때 수행시간을 증가시키고 반복문 내에서 수행시간 이전에 작업을 시작하는 task들을 전부 옮겨주고, 여기서는 또 정렬을 수행한다 
-> 정렬을 또 수행하는 이유는, 이미 수행 시점이 지난 상태라면, 이제 소요 시간이 짧은 작업이 우선적으로 처리되어야 하기 때문이다.
3. taskQueue가 비어있다면, '우선적으로 작업을 처리할게 없다'라는 의미이므로, 다음 idx 시간에 시작하는 작업을 taskQueue에 넣는다.

풀이 코드

function solution(jobs) {
    let answer = 0;
    let timer = 0;
    let taskQueue = [];
    let jobLength = jobs.length;
    
    jobs = jobs.sort((a, b) => a[0] - b[0])
    
    let idx = 0;
    while(taskQueue.length > 0 || idx < jobLength){
        
        while(idx < jobLength && jobs[idx][0] <= timer){
            taskQueue.push(jobs[idx]);
            idx++;
        }
        //소요시간 적은 순으로 정렬
        taskQueue.sort((a, b) => a[1] - b[1] || a[0] - b[1]);
        
        
        if(taskQueue.length > 0){
            let task = taskQueue.shift();
            
            timer += task[1];
            answer += timer - task[0];
        }
        else {
            timer = jobs[idx][0];
        }
    }
    
   
    
    return Math.floor(answer / jobLength);
}

결과

회고

• 반드시 정렬부터!!! 정렬안하면 틀림