AJ

안녕하세요

3 분 소요

[힙] 가운데를 말해요

문제

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.


입출력 예

입력 :

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.


출력 :

한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.


예제 입력 :

7
1
5
2
10
-99
7
5


예제 출력 :

1
1
2
2
2
2
5


풀이

힙 문제, 입력값을 최대힙이나 최소힙에 저장하며 중간값을 리턴해야 함.

처음 시도한 naive solution

let fs = require("fs");

let input = fs
  .readFileSync("test.txt")
  .toString()
  .split("\n")
  .map((el) => Number(el));

let N = input.shift();

function printMiddle(arr) {
  arr = arr.sort((a, b) => a - b);
  console.log(arr[parseInt((arr.length - 1) / 2)]);
}

for (let i = 1; i <= N; i++) {
  printMiddle(input.slice(0, i));
}
  • sort() 를 N번 사용하므로 시간복잡도는 N^2 * logN, 시간초과로 실패.
  • N은 최대 100,000 까지 입력되므로 정렬에 쓰이는 복잡도는 NlogN보다 작아야 한다.
  • 힙을 1개 만들어 입력값을 저장하고(N), 완성된 힙을 정렬한다(NlogN)해도 복잡도는 작아지지 않는다.
  • 하지만 문제에서는 전체 정렬이 필요하지 않고 중간값만 구하면 되므로, 힙을 두 개 만들고 매 입력값(N)이 두 힙 중 어느 힙에 저장될지 판별하고(1) 힙에 저장한다면(logN), 전체 NlogN 의 복잡도 안에 중간값을 구할 수 있다.
  • 따라서 중간값 양쪽에 각각 최대힙과 최소힙이 필요하며, 최소힙의 root는 최대힙의 root보다 항상 커야 한다. 
class Heap {
  constructor() {
    this.items = [];
  }
  swap(idx1, idx2) {
    [this.items[idx1], this.items[idx2]] = [this.items[idx2], this.items[idx1]];
  }
  parentIdx(idx) {
    return Math.floor((idx - 1) / 2);
  }
  leftChildIdx(idx) {
    return idx * 2 + 1;
  }
  rightChildIdx(idx) {
    return idx * 2 + 2;
  }
  parent(idx) {
    return this.items[this.parentIdx(idx)];
  }
  leftChild(idx) {
    return this.items[idx * 2 + 1];
  }
  rightChild(idx) {
    return this.items[idx * 2 + 2];
  }
  peek() {
    return this.items[0];
  }
  size() {
    return this.items.length;
  }
}

class MinHeap extends Heap {
  bubbleUp() {
    let curIdx = this.items.length - 1;
    while (
      this.parent(curIdx) !== undefined &&
      this.parent(curIdx) > this.items[curIdx]
    ) {
      this.swap(curIdx, this.parentIdx(curIdx));
      curIdx = this.parentIdx(curIdx);
    }
  }
  bubbleDown() {
    let curIdx = 0;
    while (
      (this.leftChild(curIdx) !== undefined &&
        this.leftChild(curIdx) < this.items[curIdx]) ||
      this.rightChild(curIdx) < this.items[curIdx]
    ) {
      let smallerIndex = this.leftChildIdx(curIdx);
      if (
        this.rightChild(curIdx) !== undefined &&
        this.rightChild(curIdx) < this.items[smallerIndex]
      ) {
        smallerIndex = this.rightChildIdx(curIdx);
      }
      this.swap(curIdx, smallerIndex);
      curIdx = smallerIndex;
    }
  }
  add(item) {
    this.items.push(item);
    this.bubbleUp();
  }
  removeRoot() {
    let root = this.items[0];
    this.items[0] = this.items[this.items.length - 1];
    this.items.pop();
    this.bubbleDown();
    return root;
  }
}

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

let fs = require("fs");
let input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .split("\n")
  .map((el) => Number(el));

let N = input.shift();

let max = new MaxHeap();
let min = new MinHeap();

let result = [];

for (let i = 0; i < N; i++) {
  if (max.size() > min.size()) {
    min.add(input[i]);
  } else {
    max.add(input[i]);
  }

  if (max.peek() > min.peek()) {
    let tmp = max.removeRoot();
    max.add(min.removeRoot());
    min.add(tmp);
  }
  result.push(max.peek());
}

console.log(result.join("\n"));




맨 위로

참고