절대값 힙

절댓값 힙

문제 설명

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

배열에 정수 x (x ≠ 0)를 넣는다.

배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

예제 입력

18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0

예제 출력

-1
1
0
-1
-1
1
1
-2
2
0

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(
    process.platform === "linux"
      ? "dev/stdin"
      : path.join(__dirname, "input.txt")
  )
  .toString()
  .trim()
  .split("\n");

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

  compare(a, b) {
    const absA = Math.abs(a);
    const absB = Math.abs(b);

    if (absA === absB) return a < b;
    return absA < absB;
  }

  push(num) {
    let heap = this.heap;
    heap.push(num);

    if (heap.length > 0) {
      let childIdx = heap.length - 1;
      let parentIdx = Math.floor((childIdx - 1) / 2);

      while (childIdx !== 0 && this.compare(heap[childIdx], heap[parentIdx])) {
        [heap[childIdx], heap[parentIdx]] = [heap[parentIdx], heap[childIdx]];

        childIdx = parentIdx;
        parentIdx = Math.floor((childIdx - 1) / 2);
      }
    }
  }

  pop() {
    const heap = this.heap;

    if (heap.length === 0) return 0;
    if (heap.length === 1) return heap.pop();

    const top = heap[0];
    heap[0] = heap.pop();

    let parentIdx = 0;
    let leftIdx = 1;
    let rightIdx = 2;

    while (true) {
      let smallest = parentIdx;

      if (
        heap[leftIdx] !== undefined &&
        this.compare(heap[leftIdx], heap[smallest])
      ) {
        smallest = leftIdx;
      }

      if (
        heap[rightIdx] !== undefined &&
        this.compare(heap[rightIdx], heap[smallest])
      ) {
        smallest = rightIdx;
      }

      if (smallest === parentIdx) break;

      [heap[parentIdx], heap[smallest]] = [heap[smallest], heap[parentIdx]];

      parentIdx = smallest;
      leftIdx = parentIdx * 2 + 1;
      rightIdx = parentIdx * 2 + 2;
    }
    return top;
  }
}

const solution = (input) => {
  let idx = 0;
  const absHeap = new AbsHeap();
  const N = Number(input[idx++]);
  let result = "";
  for (let i = 0; i < N; i++) {
    let el = Number(input[idx++]);

    if (el == 0) result += absHeap.pop() + "\n";
    else absHeap.push(el);
  }
  console.log(result);
};

solution(input);

아이디어 / 접근법

1. 절대값 힙
2. 0들어오면 pop
3. 아니라면 push

후기

얘는 기존 최소힙에서 두 원소의 절대값을 비교한 뒤 진행해줘야 했고 또한, 왼쪽 요소와 부모 요소, 오른쪽 요소와 부모 요소를 비교하여 최소 값을 찾아야 하는 문제였다.. 너무 어렵더라...