[백준] 1655. 가운데를 말해요 (자바스크립트/javascript/node.js/힙정렬/우선순위 큐)

 

 

 

 

문제를 풀기 위한 아이디어

힙을 이용해서 중간값을 구하는 문제이다.

이전에 블로그 포스팅으로 했었던 힙으로 중앙값찾기를 잘 연습했던 터라 이 문제는 빠르게 잘 풀 수 있었다.

다만 연습했었을 때에는 최소힙과 최대힙의 크기가 같을 때 최소힙에서 가장 작은 값, 최대힙에서 가장 큰 값을 더해서 2로 나눈 값이 중앙값이 되었다면 이번 문제에서는 둘 중 최솟값을 중앙값으로 지정하여야 한다. 이는 자바스크립트의 Math.min 메소드를 통해 쉽게 구현했다.

(제 블로그를 검색을 통해 들어온 분들은 아래의 게시글에 설명이 되어있으니 참고하시면 됩니다.)

https://nyang-in.tistory.com/155

[자바스크립트 자료구조] 힙(heap) - 연습문제

 

 

 

 

내가 작성한 코드 (자바스크립트)

class Heap {
  constructor() {
    this.items = [];
  }
  swap(index1, index2) {
    let temp = this.items[index1];
    this.items[index1] = this.items[index2];
    this.items[index2] = temp;
  }
  parentIndex(index) {
    return Math.floor((index - 1) / 2);
  }
  leftChildIndex(index) {
    return index * 2 + 1;
  }
  rightChildIndex(index) {
    return index * 2 + 2;
  }
  parent(index) {
    return this.items[this.parentIndex(index)];
  }
  leftChild(index) {
    return this.items[this.leftChildIndex(index)];
  }
  rightChild(index) {
    return this.items[this.rightChildIndex(index)];
  }
  peek() {
    return this.items[0];
  }
  size() {
    return this.items.length;
  }
}
class MinHeap extends Heap {
  //bubbleUp
  bubbleUp() {
    let index = this.items.length - 1;
    while (
      this.parent(index) !== undefined &&
      this.parent(index) > this.items[index]
    ) {
      this.swap(index, this.parentIndex(index));
      index = this.parentIndex(index);
    }
  }
  //bubbleDown
  bubbleDown() {
    let index = 0;
    while (
      this.leftChild(index) !== undefined &&
      (this.leftChild(index) < this.items[index] ||
        this.rightChild(index) < this.items[index])
    ) {
      let smallerIndex = this.leftChildIndex(index);
      if (
        this.rightChild(index) !== undefined &&
        this.rightChild(index) < this.items[smallerIndex]
      ) {
        smallerIndex = this.rightChildIndex(index);
      }
      this.swap(index, smallerIndex);
      index = smallerIndex;
    }
  }

  //add
  add(item) {
    this.items[this.items.length] = item;
    this.bubbleUp();
  }

  //poll
  poll() {
    let item = this.items[0];
    this.items[0] = this.items[this.items.length - 1];
    this.items.pop();
    this.bubbleDown();
    return item;
  }
}

class MaxHeap extends MinHeap {
  //bubbleUp
  bubbleUp() {
    let index = this.items.length - 1;
    while (
      this.parent(index) !== undefined &&
      this.parent(index) < this.items[index]
    ) {
      this.swap(index, this.parentIndex(index));
      index = this.parentIndex(index);
    }
  }
  //bubbleDown
  bubbleDown() {
    let index = 0;
    while (
      this.leftChild(index) !== undefined &&
      (this.leftChild(index) > this.items[index] ||
        this.rightChild(index) > this.items[index])
    ) {
      let largerIndex = this.leftChildIndex(index);
      if (
        this.rightChild(index) !== undefined &&
        this.rightChild(index) > this.items[largerIndex]
      ) {
        largerIndex = this.rightChildIndex(index);
      }
      this.swap(index, largerIndex);
      index = largerIndex;
    }
  }
}

class MedianHeap {
  constructor() {
    this.minheap = new MinHeap();
    this.maxheap = new MaxHeap();
  }
  add(value) {
    if (value > this.median()) {
      this.minheap.add(value);
    } else {
      this.maxheap.add(value);
    }

    if (this.minheap.size() - this.maxheap.size() > 1) {
      this.maxheap.add(this.minheap.poll());
    }
    if (this.maxheap.size() - this.minheap.size() > 1) {
      this.minheap.add(this.maxheap.poll());
    }
  }
  median() {
    if (this.minheap.size() === 0 && this.maxheap.size() === 0) {
      return Number.NEGATIVE_INFINITY;
    } else if (this.minheap.size() === this.maxheap.size()) {
      return Math.min(this.minheap.peek(), this.maxheap.peek());
    } else if (this.minheap.size() > this.maxheap.size()) {
      return this.minheap.peek();
    } else {
      return this.maxheap.peek();
    }
  }
}
let fs = require("fs");
let input = fs.readFileSync("예제.txt").toString().split("\n");
const answer = [];
const N = Number(input[0]);
input.shift();
const medianHeap = new MedianHeap();
for (let i = 0; i < N; i++) {
  medianHeap.add(Number(input[i]));
  answer.push(medianHeap.median());
}
console.log(answer.join("\n"));