[프로그래머스] 디스크 컨트롤러 (자바스크립트/js/javascript/우선순위큐/힙)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42627

코딩테스트 연습 - 디스크 컨트롤러

 

문제를 풀기 위한 아이디어

이 문제는 결국 현재 시간에서 시작할 수 있는 작업 중에 가장 작업 시간이 짧은 것을 우선적으로 처리하면 된다.

일명 SJF(Shortest Job First) 방식이라고 할 수 있다. SJF 들어본 적은 있는데 이걸 이렇게 접할 줄은 ....

일단 먼저 정렬한다. 정렬하는 순서는 jobs[index]라고 치면 jobs[index][0]을 기준으로 우선 정렬하고 같다면 jobs[index][1]을 기준으로 정렬한 후 가장 첫번째 오는 값은 가장 처음 시작하게 될 작업이다. 그리고 우선순위 큐를 만든다.

반복문을 돌면서 (반복문은 jobs를 넘지 않도록하고, 우선순위 큐 안에 값이 없을 때까지) jobs[i][0] (요청시간)이 현재시간보다 같거나 작은 아이들이 있다면 우선순위 큐에 넣어준다. 그렇게 계속 우선순위 큐에 넣어주고 넣어줄 때마다 jobs[i][1]을 기준으로 계속 정렬해준다. (작업시간을 기준으로 정렬)

그리고 우선순위 큐 안에 값이 있다면 그걸 빼내어 준다.

우선순위 큐 안에 값이 없다면 현재 인덱스가 가리키는 값을 가지고 구한다.

이 때 require > time을 넣은 이유는 현재 jobs 안에서 가리키고 있는 순서의 값이 요청시간이 현재 시간보다 늦다면 현재 시간을 요청 시간으로 바꿔주어야 하기 때문이다.

이게 무슨 말이냐면 만약 [[0,5], [2,10], [100,2]]가 예시로 주어졌을 경우 맨 처음 [0,5] 작업이 타겟이 된다. 요청시간은 0초, 작업시간은 5초, 종료시간은 0+5 = 5초, 요청부터 종료까지 걸린 시간은 5-0 = 5초, 그리고 마지막으로 현재시간은 5초가 된다. 

그 다음으로 [2,10]의 경우에는 첫번째 [0,5]작업을 하는 도중에 이미 도착해있기 때문에 첫번째 작업이 끝나고 바로 우선순위에 있었던 [2,10]을 꺼내어 처리한다. 요청시간은 2초, 작업시간은 10초, 종료시간은 현재시간 + 작업시간 = 5 + 10 = 15초, 요청부터 종료까지 걸린 시간은 15 - 2 = 13초, 현재시간은 15초가 된다.

그 다음에 이제 [100,2]를 처리하여야 하는데, 아직 현재시간은 15초인데 [100,2]작업은 100초가 되어서야 도착하기 때문에 require > time이 되므로 현재시간을 이 작업의 요청 시간으로 변경하여야 한다는 것이다.

그렇게 되면 요청 시간 : 100초, 작업 시간 : 2초, 종료 시간 : 현재 시간 + 작업 시간 = 100 + 2 = 102초, 요청부터 종료까지 걸린 시간 : 102초 - 100초 = 2초, 현재 시간 : 102초가 된다. 

따라서 요청부터 종료까지 걸린 시간만 합치면 5 + 13 + 2 = 20초 이고 20초 / 3 = 6 (소수점 제외)이 된다.

 

 

내가 작성한 코드 (자바스크립트)

function solution(jobs) {
  let answer = 0;
  jobs.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));
  let [require, work] = jobs[0];
  let end = require + work;
  let time = end;
  const priorityQueue = [];

  answer += end - require;

  let index = 1;
  while (index < jobs.length || priorityQueue.length) {
    if (index < jobs.length && jobs[index][0] <= time) {
      priorityQueue.push(jobs[index]);
      priorityQueue.sort((a, b) => a[1] - b[1]);
      index++;
      continue;
    }
    if (priorityQueue.length) {
      [require, work] = priorityQueue.shift();
      end = time + work;
      time = end;
      answer += end - require;
    } else {
      [require, work] = jobs[index];
      if (require > time) {
        time = require;
        end = time + work;
        time = end;
        answer += end - require;
      } else {
        end = time + work;
        time = end;
        answer += end - require;
      }
      index++;
    }
  }

  return Math.floor(answer / jobs.length);
}

const jobs = [
  [0, 5],
  [2, 10],
  [100, 2],
];
console.log(solution(jobs));