[Algorithm] 프로그래머스 디스크 컨트롤러 - 우선순위 큐, 힙

들어가기 전에,

이번 문제를 풀면서 우선순위 큐와 힙의 개념을 학습하고 직접 구현해보았다. 힙을 직접 구현해보며 개념을 학습하고 문제에 적용해보려고 한다.

힙 Heap

힙이란,

최댓값, 최솟값을 빠르게 구하기 위한 완전 이진 트리 자료구조이다. 힙에 데이터를 넣고 추출하는 과정은 O(logN)이 소요된다. 추출할 땐 힙의 최댓값 혹은 최솟값을 얻게 된다. 최대 힙, 최소 힙으로 분류되며 루트 노드가 최댓값 혹은 최솟값을 가지고 있다.

힙과 BST의 공통점과 차이점이 많이 언급된다. 공통점은 모두 완전 이진 트리라는 점이고, 차이점은 이진 탐색 트리의 경우 탐색을 주 목적으로 하여 가장 작은 값이 좌측에 가장 큰 값이 우측에 배치되며, 힙의 경우 루트 노드에 최솟값 혹은 최댓값이 배치된다는 점이다.

우선순위 큐는 낮은 숫자일수록 높은 우선순위를 가지므로, 이에 필요한 최소 힙을 구현해보았다.

class MinHeap {
  /**
   * @param {function(*, *): boolean} [comparator=(lhs, rhs) => lhs > rhs] sorting criteria
   */
  constructor(comparator = (lhs, rhs) => lhs < rhs) {
    this.heap = [0];
    this._comparator = comparator;
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  empty() {
    return this.heap.length === 1;
  }

  insert(data) {
    this.heap.push(data);
    const moveUp = (index = this.heap.length - 1) => {
      const parentIndex = Math.floor(index / 2);
      const parentData = this.heap[parentIndex];
      const currentData = this.heap[index];
      if (index === 1 || !this._comparator(currentData, parentData)) return;
      this.swap(index, parentIndex);
      moveUp(parentIndex);
    };
    moveUp();
  }

  extract() {
    if (this.heap.length <= 1) return;
    if (this.heap.length === 2) return this.heap.pop();
    const data = this.heap[1];
    this.heap[1] = this.heap.pop();

    const moveDown = (index = 1) => {
      const leftChildIndex = index * 2;
      const rightChildIndex = index * 2 + 1;
      const currentData = this.heap[index];
      const leftChildData = this.heap[leftChildIndex];
      const rightChildData = this.heap[rightChildIndex];
      if (!leftChildData) return;
      if (!rightChildData) {
        if (this._comparator(leftChildData, currentData)) {
          this.swap(leftChildIndex, index);
          moveDown(leftChildIndex);
        }
      } else {
        if (this._comparator(leftChildData, rightChildData)) {
          if (this._comparator(leftChildData, currentData)) {
            this.swap(leftChildIndex, index);
            moveDown(leftChildIndex);
          }
        } else {
          if (this._comparator(rightChildData, currentData)) {
            this.swap(rightChildIndex, index);
            moveDown(rightChildIndex);
          }
        }
      }
    };
    moveDown();

    return data;
  }
}

this.heap은 힙 트리를 구현하는 배열로 부모 노드와 자식 노드는 다음과 같은 인덱스에 위치한다.

const parentIndex = Math.floor(childIndex / 2);
const leftChildIndex = parentIndex * 2;
const rightChildIndex = parentIndex * 2 + 1;

this._comparator는 비교 기준이 되는 함수로 (lhs, rhs) => lhs > rhs로 변경하면 최대 힙이 된다. 어떠한 객체나 배열에서 특정 키 혹은 인덱스를 비교 기준으로 삼고 싶을 때 활용할 수 있다.

constructor(comparator = (lhs, rhs) => lhs < rhs) {
  this.heap = [0];
  this._comparator = comparator;
}

insert 메서드는 데이터를 삽입하고 힙 트리를 정렬하는 역할을 한다. 데이터를 heap 배열의 마지막에 넣으면 트리의 리프 노드가 되는데, 부모 노드와 비교하여 보다 작은 값이라면 위치를 변경하게 된다. 루트 노드에 도달하거나, 부모 노드보다 크다면(최대 힙에선 작다면) 멈추게 된다. 노드는 점점 올라가는 형태를 취하므로 함수 이름이 moveUp으로 하였다.

insert(data) {
  this.heap.push(data);
  const moveUp = (index = this.heap.length - 1) => {
    const parentIndex = Math.floor(index / 2);
    const parentData = this.heap[parentIndex];
    const currentData = this.heap[index];
    // index가 1이라면 루트 노드이다.
    // 부모 노드와 비교했을 때, 부모 노드보다 크거나 같다면 이동을 멈춘다.
    if (index === 1 || !this._comparator(currentData, parentData)) return;
    this.swap(index, parentIndex);
    moveUp(parentIndex);
  };
  moveUp();
}

extract 메서드는 힙 트리의 루트 노드, 즉 최솟값을 추출한다. 최솟값을 추출하면 트리에서 가장 큰 값(최대 힙이라면 가장 작은 값)을 루트 노드로 가져온 다음, 자식 노드와 비교하여 리프 노드에 도달하거나 자식 노드보다 모두 작을 때까지 반복한다. 노드가 점점 내려가는 형태를 취하므로 함수 이름이 moveDown으로 하였다.

extract() {
  if (this.heap.length <= 1) return;
  if (this.heap.length === 2) return this.heap.pop();
  const data = this.heap[1];
  this.heap[1] = this.heap.pop();

  const moveDown = (index = 1) => {
    const leftChildIndex = index * 2;
    const rightChildIndex = index * 2 + 1;
    const currentData = this.heap[index];
    const leftChildData = this.heap[leftChildIndex];
    const rightChildData = this.heap[rightChildIndex];
    // 완전 이진 트리이므로 좌측 자식 노드가 없다면 리프 노드이다.
    if (!leftChildData) return;
    if (!rightChildData) { // 좌측 노드만 존재할 때
      if (this._comparator(leftChildData, currentData)) {
        this.swap(leftChildIndex, index);
        moveDown(leftChildIndex);
      }
    } else { // 모든 노드가 존재할 때
      if (this._comparator(leftChildData, rightChildData)) {
        if (this._comparator(leftChildData, currentData)) {
          this.swap(leftChildIndex, index);
          moveDown(leftChildIndex);
        }
      } else {
        if (this._comparator(rightChildData, currentData)) {
          this.swap(rightChildIndex, index);
          moveDown(rightChildIndex);
        }
      }
    }
  };
  moveDown();

  return data;
}

우선순위 큐 Priority Queue

우선순위 큐란,

FIFO 정책을 가진 일반 큐와 다르게 각 자료는 우선순위를 가지고 있어서, 우선순위가 높은 순서대로 값이 추출된다. 우선순위는 힙 자료구조를 통해 관리된다. 보통 우선순위의 숫자가 작을수록 높은 우선순위로 취급하므로 최소 힙이 사용된다.

class PriorityQueue extends MinHeap {
  enqueue(data) {
    this.insert(data);
  }

  dequeue() {
    return this.extract();
  }
}

디스크 컨트롤러 - 배열로 구현

프로그래머스 - 디스크 컨트롤러 풀러가기

이 문제는 힙(Heap)으로 분류되어 있기도 하고 항상 최솟값을 선택해야 하므로 우선순위 큐를 활용하는 문제이지만, 매 순간 가장 짧은 작업 시간을 가진 작업을 선택해야 하는 그리디 문제이기도 하다.

자바스크립트에서는 우선순위 큐나 힙에 대해 구현되지 않았기에 직접 구현해야 하지만, 배열을 통해 우선순위 큐를 관리하고 작업이 추가될 때만 우선순위로 업데이트하면서 문제를 해결하려고 한다.

/**
 * heap을 통해 구현하기
 *
 * SJF(Shortest Job First) 스케줄링을 구현하는 문제이다.
 * - 작업 시간이 짧은 순서대로 작업
 * - 평균 대기 시간을 최적으로 하는 스케줄링
 * - 작업 시간을 예측해야 하는 어려움이 있지만, 이 문제에선 이미 전부 제공됨
 * - 작업을 요청 시간 순서로 담고 있는 대기열, 소요 시간이 적은 순서대로 작업을 수행하는 작업 큐가 필요
 *
 * 디스크가 작업을 수행하고 있지 않을 때 먼저 들어온 작업부터 처리하므로,
 * 작업이 요청되는 시점을 오른차순 정렬한다.
 * 작업이 요청되는 시점이 동일하다면 작업의 소요시간이 짧은 순으로 정렬한다.
 *
 * index를 통해 현재 위치의 jobs index를 기록한다.
 *
 * 먼저 들어온 작업대로 처리하면 최소 시간을 보장하지 못하므로 우선순위 큐를 사용해야 한다.
 * 우선순위에는 작업 중 가장 처리 시간이 적은 시간부터 실행해야 한다.
 *
 * [
 *   [0, 3],
 *   [1, 9],
 *   [2, 6],
 * ]
 *
 * PriorityQueue = []
 *
 * 우선순위 큐가 비었으므로 jobs의 순서대로 [0, 3]을 넣는다.
 * 시간이 3ms가 지날 동안, [1, 9]와 [2, 6]이 우선순위 큐에 할당된다.
 * [2, 6]이 더 짧은 작업 시간을 가지고 있으므로 [2, 6]이 먼저 작업되고, 그 후 [1, 9]가 작업된다.
 *
 * @param {number[][]} jobs [[작업이 요청되는 시점, 작업의 소요시간], ...]
 * @return {number} 작업의 요청부터 종료까지 걸린 최소 시간
 */
function solution(jobs) {
  jobs.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));
  const priorityQueue = [];
  let answer = 0;
  let time = 0;
  let index = 0;

  const assignTasks = () => {
    let changed = false;
    for (let i = index; i < jobs.length; ++i) {
      if (jobs[i][0] > time) break;
      priorityQueue.push(jobs[i]);
      index += 1;
      changed = true;
    }
    changed && priorityQueue.sort((a, b) => (b[1] === a[1] ? b[0] - a[0] : b[1] - a[1]));
  };

  while (index < jobs.length || priorityQueue.length) {
    if (priorityQueue.length) {
      const [startTime, executeTime] = priorityQueue.pop();
      time += executeTime;
      answer += time - startTime;
    } else {
      const [startTime, executeTime] = jobs[index++];
      time += startTime + executeTime - time;
      answer += executeTime;
    }
    assignTasks();
  }

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

SJF 스케줄링을 구현하는 문제라고 봤는데, 작업 시간이 전부 주어졌으므로 SJF의 문제점인 작업 시간을 예측해야 하는 부분은 신경쓰지 않아도 된다.
코드를 한줄씩 분석해보면,

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

문제의 조건에는 주어지지 않았지만, jobs에서 작업이 요청되는 시간과 작업에 소요되는 시간은 정렬되지 않은 상태로 주어진다. 작업이 요청되는 시간을 오름차순으로 정렬하되, 같을 경우 작업 소요 시간이 짧은 순으로 정렬했다.

const priorityQueue = [];
let answer = 0;
let time = 0;
let index = 0;

우선순위 큐를 배열로 관리하려 큐에 아이템이 추가될 때마다 우선순위 순으로 정렬해주려고 한다. SJF이므로 작업 시간이 가장 짧은 순으로 정렬해야 한다. answer는 작업이 요청되고 처리되는 평균 시간, time은 현재 시간, index는 jobs에서 처리된 곳까지의 인덱스를 나타낸다.

while (index < jobs.length || priorityQueue.length) {
  if (priorityQueue.length) {
    const [startTime, executeTime] = priorityQueue.pop();
    time += executeTime;
    answer += time - startTime;
  } else {
    const [startTime, executeTime] = jobs[index++];
    time += startTime + executeTime;
    answer += executeTime;
  }
  assignTasks();
}

index가 jobs의 길이 이상이 되면 모든 작업을 처리한 것이므로 조건을 위와 같이 설정했다. 하지만, 우선순위 큐에 아직 남은 작업이 있을 수 있으므로 우선순위 큐가 빌 때까지 반복한다. 두 조건을 or 처리한 이유는 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다. 조건 때문이다. 우선순위 큐가 비었을 땐, jobs에서 가장 먼저 들어온 요청을 처리해야 한다.

const [startTime, executeTime] = priorityQueue.pop();
time += executeTime;
answer += time - startTime;
assignTasks();

우선순위 큐가 비었을 때와 아닐 때로 구분지어 처리한다. 우선순위 큐에 대기 중인 작업 중 작업 시간이 가장 짧은 작업(이미 이 우선순위 큐는 정렬된 상태이다.)을 하나 가져와서 처리한다. 처리한 시간만큼 time이 흐르며, 현재 시간 - 작업 요청 시간을 계산하면 작업을 요청하고 처리될 때까지의 시간을 알 수 있다.

const assignTasks = () => {
  let changed = false;
  for (let i = index; i < jobs.length; ++i) {
    if (jobs[i][0] > time) break;
    priorityQueue.push(jobs[i]);
    index += 1;
    changed = true;
  }
  changed && priorityQueue.sort((a, b) => (b[1] === a[1] ? b[0] - a[0] : b[1] - a[1]));
};

assginTasks() 함수는 작업을 하나 처리할 때 동안, 그 사이에 요청된 작업을 우선순위 큐에 할당하는 역할을 담당한다. 만약, 하나의 작업을 100ms ~ 200ms 사이에 수행했다면, 이 사이에 100ms와 200ms 사이에 요청된 작업을 우선순위 큐에 추가해야 한다. 우선순위 큐에 모든 작업이 할당되면, 우선순위 큐를 작업 시간이 짧은 순서대로 정렬한다. 같은 경우엔 먼저 추가된 순서대로 정렬한다.(테스트 통과를 위해선 굳이 필요 없지만, 실제 SJF 스케줄링 환경이라면 먼저 들어온 작업이 먼저 처리되는게 효율적이다.)

우선순위 큐에 작업이 할당되지 않더라도 정렬하는 건 비효율적이므로, changed라는 플래그를 설정하여 변화가 있을 때만 정렬하도록 했다.

const [startTime, executeTime] = jobs[index++];
time += startTime + executeTime;
answer += executeTime;
assignTasks();

우선순위 큐에 대기 중인 작업이 하나도 없다면, 현재 시간 이후의 jobs에서 가장 먼저 요청된 작업이 실행된다. 대기하는 시간 + 작업 시간이 흘렀으므로 이를 time에 더해주고, 요청과 작업 시작이 동시에 이뤄지므로 작업 시간만 answer에 더해주면 된다.

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

이렇게 모든 작업을 처리하면 answer에는 작업의 요청부터 종료까지 걸린 전체 시간이므로 이를 작업의 개수로 나눠 평균을 내주면 정답이다.(소숫점 이하는 버린다.)

디스크 컨트롤러 - 힙으로 구현

시간 복잡도 측면에서 더 나아질 줄 알았는데 실제론 오히려 더 느려졌다... sort 메서드 최고..

/**
 * heap을 통해 구현하기
 *
 * @param {number[][]} jobs [[작업이 요청되는 시점, 작업의 소요시간], ...]
 * @return {number} 작업의 요청부터 종료까지 걸린 최소 시간
 */
function solution(jobs) {
  jobs.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));
  const priorityQueue = new PriorityQueue((a, b) => a[1] < b[1]);
  let answer = 0;
  let time = 0;
  let index = 0;

  const assignTasks = () => {
    for (let i = index; i < jobs.length; ++i) {
      if (jobs[i][0] > time) break;
      priorityQueue.enqueue(jobs[i]);
      index += 1;
    }
  };

  while (index < jobs.length || !priorityQueue.empty()) {
    if (priorityQueue.empty()) {
      const [startTime, executeTime] = jobs[index++];
      time = startTime + executeTime;
      answer += executeTime;
    } else {
      const [startTime, executeTime] = priorityQueue.dequeue();
      time += executeTime;
      answer += time - startTime;
    }
    assignTasks();
  }

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

class MinHeap {
  /**
   * @param {function(*, *): boolean} [comparator=(lhs, rhs) => lhs < rhs] sorting criteria
   */
  constructor(comparator = (lhs, rhs) => lhs < rhs) {
    this.heap = [0];
    this._comparator = comparator;
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  empty() {
    return this.heap.length === 1;
  }

  insert(data) {
    this.heap.push(data);
    const moveUp = (index = this.heap.length - 1) => {
      const parentIndex = Math.floor(index / 2);
      const parentData = this.heap[parentIndex];
      const currentData = this.heap[index];
      if (index === 1 || !this._comparator(currentData, parentData)) return;
      this.swap(index, parentIndex);
      moveUp(parentIndex);
    };
    moveUp();
  }

  extract() {
    if (this.heap.length <= 1) return;
    if (this.heap.length === 2) return this.heap.pop();
    const data = this.heap[1];
    this.heap[1] = this.heap.pop();

    const moveDown = (index = 1) => {
      const leftChildIndex = index * 2;
      const rightChildIndex = index * 2 + 1;
      const currentData = this.heap[index];
      const leftChildData = this.heap[leftChildIndex];
      const rightChildData = this.heap[rightChildIndex];
      if (!leftChildData) return;
      if (!rightChildData) {
        if (this._comparator(leftChildData, currentData)) {
          this.swap(leftChildIndex, index);
          moveDown(leftChildIndex);
        }
      } else {
        if (this._comparator(leftChildData, rightChildData)) {
          if (this._comparator(leftChildData, currentData)) {
            this.swap(leftChildIndex, index);
            moveDown(leftChildIndex);
          }
        } else {
          if (this._comparator(rightChildData, currentData)) {
            this.swap(rightChildIndex, index);
            moveDown(rightChildIndex);
          }
        }
      }
    };
    moveDown();

    return data;
  }
}

class PriorityQueue extends MinHeap {
  enqueue(data, key) {
    this.insert(data, key);
  }

  dequeue() {
    return this.extract();
  }
}