강의실

• https://www.acmicpc.net/problem/1374

오늘의 학습 키워드

우선순위 큐(Priority Queue)

• 우선순위에 따라서 데이터를 추출하는 자료구조
• 컴퓨터 운영체제, 온라인 게임 매칭 등에서 활용
• 일반적으로 힙(heap)을 이용해 구현한다

힙(Heap)

• 원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조
• 최대 힙(max heap) : 값이 큰 원소부터 추출
• 최소 힙(min heap) : 값이 작은 원소부터 추출
• 힙은 원소의 삽입과 삭제를 위해 O(logN)의 수행 시간을 요구
• 단순한 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일
• 이 경우 시간 복잡도는 O(NlogN)

코드

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

class MinHeap {
  #arr;

  constructor(els) {
    this.#arr = els ?? [];
  }

  enq(el) {
    this.#arr.push(el);

    let curIdx = this.#arr.length - 1;
    let parIdx = Math.floor((curIdx - 1) / 2);

    while (curIdx > 0 && this.#arr[parIdx] > this.#arr[curIdx]) {
      this._swap(curIdx, parIdx);
      curIdx = parIdx;
      parIdx = Math.floor((curIdx - 1) / 2);
    }
  }

  deq() {
    if (this.#arr.length === 0) return null;
    if (this.#arr.length === 1) return this.#arr.pop();

    const originRoot = this.#arr[0];
    this.#arr[0] = this.#arr.pop();
    let curIdx = 0;

    while (curIdx * 2 + 1 < this.#arr.length) {
      let childIdx =
        curIdx * 2 + 2 < this.#arr.length &&
        this.#arr[curIdx * 2 + 2] < this.#arr[curIdx * 2 + 1]
          ? curIdx * 2 + 2
          : curIdx * 2 + 1;

      if (this.#arr[curIdx] < this.#arr[childIdx]) {
        break;
      }

      this._swap(curIdx, childIdx);
      curIdx = childIdx;
    }
    return originRoot;
  }

  _swap(a, b) {
    const tmp = this.#arr[a];
    this.#arr[a] = this.#arr[b];
    this.#arr[b] = tmp;
  }

  get size() {
    return this.#arr.length;
  }

  get peek() {
    return this.#arr[0];
  }
}

const minHeap = new MinHeap();

const sorted = arr.sort((a, b) => a[1] - b[1]);

sorted.forEach(([_, s, t]) => {
  if (minHeap.size === 0) minHeap.enq(t);
  else {
    const head = minHeap.peek;
    if (s >= head) minHeap.deq();
    minHeap.enq(t);
  }
});

console.log(minHeap.size);

최소힙 자체는 구현한 경험이 있어서, 문제 해결 방법을 캐치한 후에는 빠르게 풀 수 있었다.