🏄🏻‍♀️ [자바스크립트] 이중 우선순위 큐

📄 문제

골드 IV 이중 우선순위 큐

구현해야 하는 것은

명렁어에 따라 최댓값을 삭제하거나 최솟값을 삭제해야 한다. 따라서 최대힙과 최소힙을 각각 구성한다. 어느 한 쪽의 힙에서 최댓(최솟)값이 제거되면 나머지 힙에서도 제거되어야 하는 값이다. 이를 위해 삽입한 값의 삭제 여부를 관리할 수 있는 객체를 생성한다.

중앙에 삽입된 값의 제거 여부를 관리하는 저장소를 두고 있고 각각의 힙에서 제거된 값이 있으면 나 이 값 제거했어! 하고 알려주면 그 저장소는 제거된 값이라는 표시로 갱신한다고 생각하면 된다.

삽입 시에는 count를 증가시키고 제거되는 시점에 count를 감소시킨다. 명령을 다 수행한 뒤에 이 저장소에 담긴 값을 활용해서 count가 0보다 큰 경우는 아직 힙에 남아있는 값이 되고, 그 중에 가장 앞에 있는 값이 최댓(최솟)값이 된다.

파라미터로 전달받은 값을 활용해서 최대 힙과 최소 힙을 각각 생성한다.

우선순위 큐의 기능을 담은 클래스를 생성하여 값을 삽입하거나 제거하며 발생하는 정렬 함수만 매개변수로 전달한다.

class PriorityQueue {
  constructor(compare) {
    this.heap = [null];
    this.compare = compare;
  }
  /* ... */
}

/* ... */

const maxHeap = new PriorityQueue((a, b) => a > b);
const minHeap = new PriorityQueue((a, b) => a < b);

/* ... */

최대값 또는 최소값이 큐에서 제거되면 제거되었음을 저장할 객체가 필요하다.

최대값을 삭제하는 연산(D 1)은 최대힙에서만 값이 삭제되고, 최소값을 삭제하는 연산(D -1) 역시 최소힙에서만 값이 삭제된다. 그렇기 때문에 상대힙에게 제거된 값을 알려주기 위해 제거되었음을 담고 있을 객체를 생성해야 한다.

값을 삽입하는 연산(I 정수N)을 수행할 때 해당 정수값이 삽입되었음을 아래처럼 저장해둔다.

const valid = {};

if (command === "I") {
  maxHeap.push(+num);
  minHeap.push(+num);

  // 👇 삽입된 값의 count를 증가시킨다. 특정 정수가 삽입되면 { num : 1 } 이런 식으로 저장된다.
  valid[+num] = (valid[+num] || 0) + 1;
}

그리고 삭제 연산이 발생한 경우 이 count를 감소시키면 된다.

즉 I 100 연산으로 최대/최소힙에 1이라는 값이 삽입되면 { 100 : 1 }이 될 것이고, D 연산으로 어느 힙에서든 100이라는 값이 제거가 된다면 { 100 : 0 }이 된다.

그러므로 제거하려는 값의 count를 확인했는데 0이면 상대 힙에서 이미 제거했다는 의미다. 그러므로 본인의 리스트에서도 그 값을 제거한 후에 양쪽에서 제거되지 않은 값을 찾을 때까지 계속 dequeue 작업을 해줘야 한다.

while (!heap.empty()) {
  const popedItem = heap.pop();

  // 👇 0보다 큰다는 것은 최대/최소힙에 아직 남아있는 값이다.
  if (valid[popedItem] > 0) {
    valid[popedItem]--;
    break;
  }
}

명령어를 모두 수행한 뒤에 최대/최소힙에 남은 값과 그 값의 삭제 여부를 확인해서 삭제되지 않았고 힙에서 가장 앞에 있는 값을 출력하면 된다.

// 👇 힙의 가장 첫 번째 값의 제거 여부를 확인 후에 제거되지 않은 값을 찾을 때까지 dequeue 작업을 반복한다.
while (!heap.empty() && valid[heap.top()] === 0) {
  heap.pop();
}

// 👇 힙이 둘 다 비어있으면 EMPTY를 출력한다.
if (maxHeap.empty() && minHeap.empty()) {
  result.push("EMPTY");
} else {
  // 👇 top()으로 각 힙에서 가장 첫 번째에 있는 값을 출력한다.
  result.push(`${maxHeap.top()} ${minHeap.top()}`);
}

🏹 코드

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

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

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

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

  top() {
    return this.heap[1];
  }

  push(item) {
    this.heap.push(item);
    this.heapifyUp();
  }

  heapifyUp() {
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);

    while (
      currentIndex > 1 &&
      this.compare(this.heap[currentIndex], this.heap[parentIndex])
    ) {
      this.swap(currentIndex, parentIndex);

      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }

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

    this.heapifyDown();
    return result;
  }

  heapifyDown() {
    let currentIndex = 1;
    let leftChildIndex = currentIndex * 2;
    let rightChildIndex = currentIndex * 2 + 1;

    if (!this.heap[leftChildIndex]) return;

    while (
      currentIndex < this.heap.length &&
      (this.compare(this.heap[leftChildIndex], this.heap[currentIndex]) ||
        this.compare(this.heap[rightChildIndex], this.heap[currentIndex]))
    ) {
      let compareIndex;

      if (rightChildIndex > this.heap.length - 1) {
        compareIndex = leftChildIndex;
      } else {
        compareIndex = this.compare(
          this.heap[leftChildIndex],
          this.heap[rightChildIndex]
        )
          ? leftChildIndex
          : rightChildIndex;
      }

      this.swap(currentIndex, compareIndex);

      currentIndex = compareIndex;
      leftChildIndex = currentIndex * 2;
      rightChildIndex = currentIndex * 2 + 1;
    }
  }
}

let maxHeap = new PriorityQueue((a, b) => a > b);
let minHeap = new PriorityQueue((a, b) => a < b);
let valid = {};
const result = [];
let t = null,
  k = 0;

const enqueue = (value) => {
  // 👇 최대/최소힙에 값을 삽입하고 값의 삭제 여부를 관리하는 객체(valid)에 삽입되었음(count 증가)으로 갱신한다.
  maxHeap.push(value);
  minHeap.push(value);

  valid[value] = (valid[value] || 0) + 1;
};

const dequeue = (heap) => {
  // 👇 제거하려던 값이 다른 힙에서 이미 제거된 값이면 본인 힙에서도 제거한 후에 아직 양쪽 힙에 남아있는 값을 찾아서 제거한다.
  while (!heap.empty()) {
    const popedItem = heap.pop();
    if (valid[popedItem] > 0) {
      valid[popedItem]--;
      break;
    }
  }
};

const removeDummyDataInHeap = (heap) => {
  // 👇 현재 힙의 첫 번째 값이 제거된 값인지 확인하고 유효한 값이 나올 때까지 필요없는 값은 제거한다.
  while (!heap.empty() && valid[heap.top()] === 0) {
    heap.pop();
  }
};

rl.on("line", (line) => {
  if (!t) {
    t = +line;
    return;
  }
  if (k === 0) {
    k = +line;
    maxHeap = new PriorityQueue((a, b) => a > b);
    minHeap = new PriorityQueue((a, b) => a < b);
    valid = {};
    return;
  }

  const [command, num] = line.split(" ");

  if (command === "I") {
    enqueue(+num);
  } else if (+num === 1) {
    dequeue(maxHeap);
  } else if (+num === -1) {
    dequeue(minHeap);
  }

  if (--k === 0) {
    removeDummyDataInHeap(maxHeap);
    removeDummyDataInHeap(minHeap);

    if (maxHeap.empty() && minHeap.empty()) {
      result.push("EMPTY");
    } else {
      result.push(`${maxHeap.top()} ${minHeap.top()}`);
    }
  }
}).on("close", () => {
  console.log(result.join("\n"));
  process.exit();
});

🤦🏻‍♀️ 시행착오

최대 값과 최소 값을 각각 어떻게 관리할까

처음에는 하나의 우선순위 큐로 최대값과 최소값을 제거해나가면서 최종적인 답을 찾으려고 했는데 도저히 생각이 나지 않았다. 그래서 검색해보니 최대/최소힙을 각자 구성하고 따로 객체 생성해서 제거된 값을 관리하는 방법을 찾았다.

🐝 참고

[백준] 이중 우선순위 큐(7662)

메모리 초과가 계속 발생한다면 모듈 확인하기

3개월 전에 실패하고 3주 전에도 실패하며 오늘은 꼭 해결해야겠다 생각하며 반나절을 다 보냈다. 계속 메모리 초과가 발생했고 원인을 찾으려고 한 줄씩 주석치면서 찾았지만 결국 찾지 못했고 다른 분의 코드를 보면서 fs 모듈이 아닌 readline 모듈을 사용해야 한다는 것을 알 수 있었다.

가끔 백준 문제를 풀 때 모듈 사용으로 인해 시간을 많이 소요하면 힘이 빠질 때도 있지만.. 자주 안풀어서 까먹었던 내 탓이니까..