디스크 컨트롤러

디스크 컨트롤러

const SimplePQ = {
  init: function () {
    this.values = [];
  },
  enqueue: function (start, priority) {
    this.values.push([start, priority]);
    this.values.sort((a, b) => a[1] - b[1]);
  },
  dequeue: function () {
    return this.values.shift();
  },
};

function solution(jobs) {
  // 요청이 들어온 순서대로 정렬
  // 비선점방식이기에 하드디스크가 작업을 수행하지 않고 있을 때에는
  // 먼저 들어온 작업을 처리해주어야 하기 때문
  jobs.sort((a, b) => a[0] - b[0]);

  // 우선순위 큐 초기화
  const spq = Object.create(SimplePQ);
  spq.init();

  // 현재 시간 기록
  let time = 0;

  // 평균 구하기 위한 합계 기록
  let sum = 0;

  // 평균 구하기 위한 분모의 역할 && 반복문 기저 조건
  let done = 0;
  const limit = jobs.length;

  // jobs에서 우선순위 큐로 삽입
  function enqueue() {
    while (jobs.length && jobs[0][0] <= time) {
      spq.enqueue(...jobs.shift());
    }
  }

  while (done < limit) {
    // 우선순위 큐로의 삽입은 대기열에 대기하고 있는 작업이 있는 것이 전제
    if (jobs.length) {
      if (jobs[0][0] <= time) {
        // 현재 시점에서 대기열의 작업 중 이미 요청된 것이 있다면,
        // 현재 우선순위 큐에 있는 작업보다 소요시간이 더 짧은 것이 있을 수 있으므로
        // 우선순위 큐를 갱신해주어야 한다.
        enqueue();
      } else if (!spq.values.length) {
        // 현재 시점에서 대기열의 작업 중에서 아직 요청된 것이 없다면,
        // 두 가지 상황으로 나눌 수 있다.
        // 1. 우선순위 큐에 작업이 있는 상황
        // 2. 우선순위 큐에 작업이 없는 상황
        // 1번의 상황에서는 바로 우선순위 큐 작업을 처리해준 뒤 다시 대기열을 확인하면 되고,
        // 2번의 상황에서는 대기열의 작업을 처리할 수 있는 시점으로 건너가 큐를 갱신해주면 된다.
        time = jobs[0][0];
        enqueue();
      }
    }

    const [start, duration] = spq.dequeue();
    time += duration;
    sum += time - start;
    done++;
  }
  return Math.floor(sum / done);
}

• 직접 구현한 우선순위 큐를 적용하니 시간초과가 뜬다;;

• 시간 복잡도 때문이 아니라 특정 예외처리가 누락되어 무한 반복을 도는 게 아닌가 싶은데, 누락된 예외처리가 뭔질 모르겠다 ㅠ