[백준] 절댓값 힙 #11286

설명

c++의 priority_queue를 이용해서 풀었다.
해당 자료구조의 사용법을 익힐 수 있는 문제였다.(compare 구조체 관련)

이 문제는 JS에서 priority queue가 없어 나중에 priority queue 자료구조를 직접 만든 다음에 다시 풀어서 다시 글을 작성할 예정이다.

JS에서 Priority Queue를 구현했다. 자료구조 구현과 관련해서는 다른 글에서 자세히 적는 것으로 하고, 자료구조 구현후 C++을 풀었을 때와 동일하게 푸니 바로 정답이 떴다.

Node.js 풀이

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

const N = Number(input[0]);
const commands = input.slice(1).map(Number);

class PriorityQueue {
  constructor(compare = (a, b) => a > b) {
    this.heap = [];
    this.compare = compare;
  }
  top() {
    if (this.empty())
      throw new Error(`[TOP ERROR]: PriorityQueue's size is empty.`);
    return this.heap[0];
  }
  empty() {
    return this.size === 0;
  }
  push(node) {
    this.heap.push(node);
    this.heapifyUp();
  }
  pop() {
    if (this.empty())
      throw new Error(`[POP ERROR]: PriorityQueue's size is empty.`);
    [this.heap[0], this.heap[this.size - 1]] = [
      this.heap[this.size - 1],
      this.heap[0],
    ];
    const target = this.heap.pop();
    this.heapifyDown();
    return target;
  }
  heapifyUp() {
    let cur = this.size - 1;
    while (cur !== 0) {
      let parent = Math.floor((cur - 1) / 2);
      if (!this.compare(this.heap[cur], this.heap[parent])) break;
      [this.heap[cur], this.heap[parent]] = [this.heap[parent], this.heap[cur]];
      cur = parent;
    }
  }
  heapifyDown() {
    let cur = 0;
    while (cur * 2 + 1 < this.size) {
      let left = cur * 2 + 1;
      let right = cur * 2 + 2;
      let max = left;
      if (this.heap[right] && !this.compare(this.heap[left], this.heap[right]))
        max = right;
      if (!this.compare(this.heap[max], this.heap[cur])) break;
      [this.heap[cur], this.heap[max]] = [this.heap[max], this.heap[cur]];
      cur = max;
    }
  }
  get size() {
    return this.heap.length;
  }
}

const solution = (N, commands) => {
  const pq = new PriorityQueue((a, b) => {
    if (Math.abs(a) !== Math.abs(b)) return Math.abs(a) < Math.abs(b);
    return a < b;
  });
  let answer = '';
  commands.forEach((command) => {
    if (command !== 0) {
      pq.push(command);
    } else {
      if (pq.empty()) answer += '0\n';
      else answer += pq.pop() + '\n';
    }
  });
  return answer;
};

console.log(solution(N, commands));

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

struct compare {
    bool operator()(int n1, int n2) {
        if (abs(n1) == abs(n2)) return n1 > n2;
        return abs(n1) > abs(n2);
    }
};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    priority_queue<int, vector<int>, compare> PQ;
    while(N--) {
        int cmd; cin >> cmd;
        if (cmd != 0) PQ.push(cmd);
        else {
            if (PQ.empty()) {
				cout << '0' << '\n';
				continue;
			}
            cout << PQ.top() << '\n';
            PQ.pop();
        }
    }
    return 0;
}