문제
https://www.acmicpc.net/problem/1655
아이디어
힙을 이용하면 값을 최대 값 혹은 최소 값부터 구해낼 수 있다.
그런데 여기서는 숫자의 양 끝인 최소나 최대를 구하는 것이 아니라, 가운데에 있는 값을 구해야 한다.
이런 문제를 해결하는 방법은 숫자를 하나의 힙에 보관하는 것이 아니라, 왼쪽 부분을 담당하는 힙과 오른쪽 부분을 담당하는 힙으로 두 개 만들어 놓고 숫자를 추가할 때 마다 두 힙에 나눠서 넣는 방법을 사용하면 된다.
낮은 숫자들이 나열되어 있는 왼쪽 부분의 힙을 최대 힙으로 만들면, 항상 최대 힙의 루트 노드는 전체 숫자에서의 가운데 부분을 담당하게 된다.
마찬가지로 높은 숫자들이 나열되어 있는 오른쪽 부분의 힙을 최소 힙으로 만들면, 항상 최소 힙의 루트 노드는 전체 숫자에서의 가운데 부분을 담당하게 된다.
다만 최대 힙이 반드시 왼쪽 부분이 되고 최소 힙이 반드시 오른쪽 부분이 되기 위해서는 어떠한 최대 힙 안에 존재하는 숫자도 최소 힙 안에 존재하는 숫자보다는 작아야 한다.
이를 보장하기 위해서 숫자를 힙에 추가할 때 마다 최대 힙의 루트 노드와 최소 힙의 루트 노드를 비교하여 최대 힙의 루트 노드가 더 크다면 최대 힙과 최소 힙에 존재하는 루트 노드를 꺼내서 서로 교환한다.
백준이가 숫자를 외칠 때마다 힙에 숫자를 추가한다.
- 최대 힙에 우선적으로 넣는다.
- 최대 힙과 최소 힙에 존재하는 원소 갯수의 차이는 한 개를 초과해서는 안된다.
- 만약 최대 힙의 루트 노드가 최소 힙의 루트 노드보다 크다면, 각 힙에 있는 루트 노드를 꺼내서 서로 교환한다.
- 가장 가운데 값인
max.heap[1]을 결과 배열에 추가한다.
소스코드
// 입력 처리
const INPUT_NAME = 'i2.txt';
const filePath =
process.platform === 'linux'
? '/dev/stdin'
: `./boj/${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require('fs')
.readFileSync(filePath)
.toString()
.trim()
.split('\n')
.map(item => item.trim());
const n = Number(input[0]);
class Heap {
constructor(order) {
this.heap = [null];
this.order = order;
}
needToSwap(parent, child) {
if (this.order === 'min') return this.heap[parent] > this.heap[child];
else if (this.order === 'max') return this.heap[parent] < this.heap[child];
}
nextChildIsPrior(child) {
if (this.order === 'min') return this.heap[child] > this.heap[child + 1];
else if (this.order === 'max') return this.heap[child] < this.heap[child + 1];
}
size() {
return this.heap.length - 1;
}
push(value) {
this.heap.push(value);
let child = this.heap.length - 1;
while (child > 1) {
let parent = Math.floor(child / 2);
if (!this.needToSwap(parent, child)) break;
[this.heap[parent], this.heap[child]] = [this.heap[child], this.heap[parent]];
child = parent;
}
}
pop() {
if (this.heap.length <= 1) return;
if (this.heap.length === 2) return this.heap.pop();
const result = this.heap[1];
this.heap[1] = this.heap.pop();
let parent = 1;
let child = 2;
while (child < this.heap.length) {
if (child + 1 < this.heap.length && this.nextChildIsPrior(child)) child++;
if (!this.needToSwap(parent, child)) break;
[this.heap[parent], this.heap[child]] = [this.heap[child], this.heap[parent]];
parent = child;
child *= 2;
}
return result;
}
}
// 풀이
function solution() {
const max = new Heap('max');
const min = new Heap('min');
const result = [];
// 백준이가 외치는 숫자마다 반복한다.
for (let i = 1; i <= n; i++) {
const now = Number(input[i]);
// 숫자는 최대 힙에 우선적으로 넣되, 최대 힙과 최소 힙에 서로 번갈아가면서 숫자를 넣는다.
if (max.size() === 0 || max.size() === min.size()) max.push(now);
else min.push(now);
// 숫자의 왼편을 담당하는 최대 힙은 항상 숫자의 오른편을 담당하는 최소 힙의 숫자보다는 작아야 한다.
// 그러므로, 최대 힙에 들어간 최대 값이 최소 힙에 들어간 최소 값보다 크다면 그 둘을 꺼내서 서로 스왑해준다.
if (max.size() !== 0 && min.size() !== 0 && max.heap[1] > min.heap[1]) {
let maxValue = max.pop();
let minValue = min.pop();
max.push(minValue);
min.push(maxValue);
}
result.push(max.heap[1]);
}
console.log(result.join('\n'));
}
// 실행
solution();