문제 개요

문제: 강의실 배정

분류: 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐

난이도: 골드5

문제 풀이

최소힙을 가지는 우선순위 큐를 사용하여 풀 수 있다.

1. 강의를 시작 시간 순으로 정렬한다.
2. 첫 번째 강의가 끝나는 시간을 우선순위 큐에 넣는다.
3. 두 번째 강의부터 마지막 강의까지 아래를 반복한다.
   1. 우선순위 큐의 가장 앞에 있는 값이 현재 강의가 시작하는 시간보다 작거나 같은 경우 우선순위 큐를 pop한다.
   2. 현재 강의가 끝나는 시간을 우선순위 큐에 넣는다.

모든 과정이 끝난 후 우선순위 큐에 남은 원소의 개수, 즉 우선순위 큐의 크기가 최소 강의실 수가 된다.

💡 왜 강의를 시작 시간 순으로 정렬하는가?
강의실 수를 ‘최소’로 만들기 위해서이다. 위 풀이에서는 같은 강의실을 사용할 수 있는 강의를 찾았을 때 이미 큐에 들어가있던 강의를 ‘제거’하는 방식을 사용한다. 따라서 오름차순 정렬을 하지 않는다면 어떤 강의 a와 같은 강의실을 사용할 수 있는 b를 찾으면 두 강의 사이에 빈 시간이 아무리 많더라도 a를 이미 큐에서 제거해버리기 때문에 강의실의 개수를 최소로 만들 수 없다.

아래 그림은 어떤 예시에 대해 위 풀이 방식을 적용했을 때 오름차순 정렬을 하지 않은 경우와 한 경우의 차이를 표현한 그림이다.

💡 왜 최소힙을 사용하는가?
마찬가지로 강의실 수를 ‘최소’로 만들기 위함이다. 풀이에 따르면 우선순위 큐에는 강의가 ‘끝나는’ 시간을 저장한다. 현재 큐에 남아있는 강의 중 끝나는 시간이 가장 이른 강의와 현재 강의를 비교해야 강의실 수를 최소로 만들 수 있다.

예제 입력1에 대한 풀이

강의를 시작 시간을 기준으로 오름차순 정렬한 후, 첫번째 강의의 끝나는 시간을 우선순위 큐에 push한다.

이후 두 번째 강의부터 시작 시간을 우선순위 큐의 가장 앞에 있는 값과 비교한다.

우선순위 큐의 가장 앞에 있던 3(1번 강의의 끝시간)과 현재 강의의 시작 시간인 2를 비교했을 때 2번 강의가 시작한 후에 1번 강의가 끝나기 때문에 pop하는 것 없이 현재 강의의 끝시간 4를 우선순위 큐에 push한다.

다음으로 세 번째 강의의 시작 시간을 우선순위 큐의 가장 앞에 있던 3과 비교한다.

이때 두 값이 같기 때문에 1번 강의와 3번 강의는 같은 강의실을 쓸 수 있게 된다. 따라서 우선순위 큐를 pop한 후 현재 강의의 끝나는 시간인 5를 우선순위 큐에 push한다.

모든 강의에 대한 수행이 끝났기 때문에 현재 우선순위 큐 [4, 5]의 크기 2가 최소로 사용할 수 있는 강의실의 수이다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const [N, ...time] = fs.readFileSync(filePath).toString().trim().split("\n");

class PriorityQueue {
  constructor() {
    this.heap = [];
  }

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

  peek() {
    return this.heap[0];
  }

  size() {
    return this.heap.length;
  }

  push(data) {
    this.heap.push(data);

    let i = this.heap.length - 1;
    while (i > 0) {
      const parent = ~~((i - 1) / 2);
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }

  pop() {
    if (this.empty()) return;

    const value = this.peek();
    [this.heap[0], this.heap[this.heap.length - 1]] = [
      this.heap[this.heap.length - 1],
      this.heap[0],
    ];

    this.heap.pop();
    this._heapify();
    return value;
  }

  _heapify() {
    const x = this.peek();
    const n = this.heap.length;
    let curr = 0;

    while (2 * curr + 1 < n) {
      const leftChild = 2 * curr + 1;
      const rightChild = leftChild + 1;
      const smallerChild =
        rightChild < n && this.heap[rightChild] < this.heap[leftChild]
          ? rightChild
          : leftChild;

      if (x > this.heap[smallerChild]) {
        [this.heap[curr], this.heap[smallerChild]] = [
          this.heap[smallerChild],
          this.heap[curr],
        ];
        curr = smallerChild;
      } else break;
    }
  }
}

const solution = (N, time) => {
  const lectures = time.map((t) => t.split(" ")).map((t) => t.map(Number));
  lectures.sort((a, b) => a[0] - b[0]);

  const pq = new PriorityQueue();
  pq.push(lectures[0][1]);

  for (let i = 1; i < +N; i++) {
    if (pq.peek() <= lectures[i][0]) {
      pq.pop();
    }
    pq.push(lectures[i][1]);
  }

  console.log(pq.size());
};

solution(N, time);