🏄🏻‍♀️ [자바스크립트] 디스크 컨트롤러

📄 문제

프로그래머스 디스크 컨트롤러

구현해야 하는 것은

파라미터로 전달받은 작업 목록(jobs)을 어떤 순서대로 처리해야 가장 최소의 평균시간을 찾을 수 있는지를 파악해야 한다.

수행중인 작업이 없다면 먼저 들어온 작업을 우선 처리해야 하고, 수행중인 작업이 있으면 그 작업이 끝나는 시점까지 들어오는 요청들을 처리시간의 오름차순으로 정렬해서 대기열에 삽입 후 순서대로 수행한다.

jobs의 요소는 [작업이 요청되는 시점, 작업의 소요시간] 형태이므로 작업이 요청되는 시점으로 언제 대기열에 넣을 것인지, 작업의 소요시간으로 대기열 내에서의 수행 순서를 계산한다.

중요한 점은 작업 목록 jobs는 요청 시간이 정렬되어 있지 않다. (예) [[7, 8], [3, 5], [9, 6]]) 수행중인 작업이 없다면 먼저 들어온 작업을 우선 처리해야 하므로 요청 시간의 오름차순으로 정렬하도록 한다.

1️⃣ 파라미터로 받은 배열을 순회하며 조건에 따라 새로운 배열에 삽입하고 정렬하기 위해 필요한 변수를 선언한다.

const solution = (jobs) => {
  // 작업의 대기열 역할을 할 변수 선언 및 초기화를 수행한다.
  const priorityQueue = [];

  // time : 작업을 수행하며 현재 시점이 언제인지 저장한다. 즉, 처음 0ms에서 시작하여 3ms만큼 걸리는 작업을 수행하면 time을 3으로 갱신한다.
  // index : jobs를 반복하기 위한 인덱스다.
  // result : 각 작업의 총 수행 시간을 누적한다. 총 소요 시간은 작업 처리 시간과 대기 시간을 더한 값이다. 추후 평균 시간을 계산하기 위해 사용한다.
  let time = 0,
    index = 0,
    result = 0;
};

2️⃣ 먼저 들어온 작업을 우선 처리하기 위해 요청 시간의 오름차순 정렬한다.

수행중인 작업이 없다면 먼저 들어온 작업을 우선 처리해야 하므로 요청 시간이 빠른 순으로 정렬이 필요하다.

요소 형태는 [작업이 요청되는 시점, 작업의 소요시간]이므로 0번째 요소로 비교한다.

[[7, 8], [3, 5], [9, 6]]라는 작업 목록이 전달되면 [[3, 5], [7, 8], [9, 6]]로 정렬된다. 이 작업 목록은 3ms에 처음 작업 요청을 한 것이다.

jobs.sort((a, b) => a[0] - b[0]);

3️⃣ 현재 시점 이전에 들어온 작업을 대기열에 삽입하고, 대기열 내에서 가장 소요 시간이 짧은 작업을 앞으로 보낸다.

// 현재 시점과 가장 빠른 요청 시간이 같거나 크면 현재 시점 이전에 들어온 작업을 대기열에 삽입한다.
if (index < jobs.length && time >= jobs[index][0]) {
    priorityQueue.push(jobs[index++]);

    // 짧은 소요시간이 먼저 처리되어야 하므로 소요시간의 오름차순으로 정렬한다.
    priorityQueue.sort((a, b) => a[1] - b[1]);

    continue;
}

4️⃣ 대기열에 있는 작업을 수행하며 시점과 총 작업 시간을 갱신한다.

현재 시점에서 대기열로 추가할 작업이 없다면 가장 짧은 시간이 소요되는 작업을 수행해야 하는 시점이므로 대기열의 첫 번째 요소를 제거한다. 작업이 수행된 것이므로 작업이 완료된 후의 시점과 해당 작업에 소요된 시간을 계산하여 각각 변수에 가산한다.

if (priorityQueue.length > 0) {
  const [requestTime, workingTime] = priorityQueue.shift();
  time += workingTime;
  result += time - requestTime;
}

5️⃣ 현재 시점 기준 이전에 들어온 작업이 없고, 대기열에서 수행할 작업이 없다면

현재 방문한 jobs 요소의 요청 시간을 현재 시점으로 업데이트한다.

예를 들어, [[3, 5], [7, 8], [9, 6]]라는 작업 목록은 첫 번째로 수행할 작업이 3ms 시점에 요청한다. 현재 시점이 0ms라면 현재 시점을 3ms로 업데이트 후 대기열에 삽입 및 처리할 수 있도록 한다.

else {
  time = jobs[index][0];
}

🏹 코드

우선순위 큐로 구현하려고 했는데 막혀서 다른 블로그에서 배열을 활용한 풀이를 참고해서 해결했다.

🐝 참고

[프로그래머스/Javascript] 디스크 컨트롤러

const solution = (jobs) => {
  const priorityQueue = [];

  let time = 0,
    index = 0,
    result = 0;

  jobs.sort((a, b) => a[0] - b[0]);

  // jobs 순회를 끝내지 않았거나 대기열이 비어있지 않으면 작업을 계속 수행한다.
  while (index < jobs.length || priorityQueue.length > 0) {
    if (index < jobs.length && time >= jobs[index][0]) {
      priorityQueue.push(jobs[index++]);
      priorityQueue.sort((a, b) => a[1] - b[1]);

      continue;
    }

    if (priorityQueue.length > 0) {
      const [requestTime, workingTime] = priorityQueue.shift();
      time += workingTime;
      result += time - requestTime;
    } else {
      time = jobs[index][0];
    }
  }

  // result는 각 작업의 총 소요 시간을 누적되어있으므로 평균을 위해 작업의 수만큼 나눈 후 반환한다.
  return parseInt(result / jobs.length);
};

⛳️ 더 좋은 해결책

위에서 언급한대로 원래는 힙으로 구현하려고 하였다. 클래스로 Heap을 선언하고 작업 목록을 순회하며 해결한 포스트를 발견하여 남겨둔다.

Heap 클래스를 사용하면 배열의 shift나 sort 작업을 하지 않으므로 더 빠르다.

(참고 : 배열로 구현한 코드를 참고한 블로그의 댓글)

직접 각각의 코드를 돌려보면 아래와 같이 나온다. 테스트 케이스를 알 수 없으나, 중간중간 힙을 사용할 것과 배열로 사용한 것의 시간이 크게 차이나는 케이스가 보이는데 아마 작업 데이터가 많이 들어온 케이스가 아닐까 생각이 든다. 더 좋은 해결책이라기 보다는 내가 해결하지 못한 방법으로 충분히 해결 가능하다는 것을 인지하기 위해 남겨둔다!

🐝 참고

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