[BOJ 11286] 절댓값 힙 (nodejs)

https://www.acmicpc.net/problem/11286

처음에 문제를 보고 최소힙에서 비교하는 부분만 절댓값을 씌워서 하면 풀리는 줄 알았다..

이후에 절댓값이 같더라도 삽입시에 부모 요소와 현재 요소의 경우의 수를 따지고, 제거 시에 부모 요소와 자식 둘 요소를 비교하는 경우를 모두 따져야 한다.

경우의 수를 나눠보자.

• 부모요소의 절댓값 > 자식요소의 절댓값
  - 부모와 자식의 자리를 바꾼다.(삭제의 경우 왼/오른쪽 자식을 비교하여 더 작은 놈과 바꾼다)
• 부모요소의 절댓값 = 자식요소의 절댓값
  • 부모요소의 값 > 자식요소의 값
    • 부모와 자식의 자리를 바꾼다.(삭제의 경우 왼/오른쪽 자식을 비교하여 더 작은 놈과 바꾼다)
  • 부모요소의 값 < 자식요소의 값
    • 그대로 둔다.
  • 부모요소의 값 = 자식요소의 값
    • 그대로 둔다.
• 부모요소의 절댓값 < 자식요소의 절댓값
  - 그대로 둔다.
  

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const N = +input[0];

const heap = [];
let size = 0;

const swap = (idx1, idx2) => {
  let tmp = heap[idx1];
  heap[idx1] = heap[idx2];
  heap[idx2] = tmp;
};

const comp = (a, b) => {
  // a 가 클때 true 리턴
  if (Math.abs(heap[a]) === Math.abs(heap[b])) {
    if (heap[a] > heap[b]) return true;
    else return false;
  } else if (Math.abs(heap[a]) > Math.abs(heap[b])) {
    return true;
  } else {
    return false;
  }
};

const push = (x) => {
  if (size === 0) heap[1] = x;
  else {
    let pos = size + 1;
    heap[pos] = x;
    while (comp(Math.floor(pos / 2), pos) && pos !== 1) {
      swap(pos, Math.floor(pos / 2));
      pos = Math.floor(pos / 2);
    }
  }
  size++;
};

const top = () => {
  if (size === 0) return 0;
  return heap[1];
};

const pop = () => {
  if (size === 0) return;
  let pos = 1;
  heap[pos] = heap[size];
  heap.pop();
  while (
    (heap[pos * 2] && comp(pos, pos * 2)) ||
    (heap[pos * 2 + 1] && comp(pos, pos * 2 + 1))
  ) {
    if (comp(pos * 2, pos * 2 + 1)) {
      swap(pos, pos * 2 + 1);
      pos = pos * 2 + 1;
    } else {
      swap(pos, pos * 2);
      pos = pos * 2;
    }
  }
  size--;
};

let res = "";

for (let i = 1; i <= N; i++) {
  let num = +input[i];

  if (num === 0) {
    res += top() + "\n";
    pop();
  } else {
    push(num);
  }
}
console.log(res);

핵심은 comp()함수에 있다.

comp() 함수는 자리를 바꿔야 할 때 true를 반환하는데 위에서 나열하였듯이 두가지 경우가 존재한다.
1. 부모의 절댓값이 자식의 절댓값 보다 큰 경우
2. 부모의 절댓값이 자식의 절댓값과 같은데 부모의 값이 큰 경우

const comp = (a, b) => {
  // a 가 클때 true 리턴
  if (Math.abs(heap[a]) === Math.abs(heap[b])) {
    if (heap[a] > heap[b]) return true;
    else return false;
  } else if (Math.abs(heap[a]) > Math.abs(heap[b])) {
    return true;
  } else {
    return false;
  }
};