문제 설명
최소 힙을 이용해 연산을 처리하는 프로그램을 작성하는 문제
예제 입력/출력
•
입력1
9
0
12345678
1
2
0
0
0
0
32
Plain Text
복사
•
출력1
0
1
2
12345678
0
Plain Text
복사
제약 조건
•
◦
문제 풀이
힙 클래스 초기화
최소 힙의 부모와 자식 간에 다음과 같은 관계가 성립한다.
•
부모의 인덱스 = Math.floor((자식의 index - 1) / 2)
•
왼쪽 자식의 인덱스 = 2 * 부모의 index + 1
•
오른쪽 자식의 인덱스 = 2 * 부모의 index + 2
class MinHeap {
constructor() {
this.heap = [];
}
getParentIndex(index) {
return Math.floor((index - 1) / 2);
}
getLeftChildIndex(index) {
return 2 * index + 1;
}
getRightChildIndex(index) {
return 2 * index + 2;
}
size() {
return this.heap.length;
}
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
}
JavaScript
복사
삽입 연산
MinHeap의 삽입 연산은 다음과 같은 단계로 이루어진다.
1.
Heap의 마지막 위치에 요소를 추가한다.
2.
새로운 요소를 추가한 위치에서부터, 부모 노드와 새로 추가된 노드의 값을 비교한다. 만약 새로 추가된 노드의 값이 부모 노드의 값보다 작다면, 부모 노드와 새로 추가된 노드의 위치를 교환한다.
3.
이전 단계에서 교환된 새로 추가된 노드와 부모 노드의 값 비교를 반복한다.
heappush(value) {
this.heap.push(value);
this.heapifyUp();
}
heapifyUp() {
let index = this.size() - 1;
while(index > 0 && this.heap[this.getParentIndex(index)] > this.heap[index]) {
this.swap(index, this.getParentIndex(index));
index = this.getParentIndex(index);
}
}
JavaScript
복사
삭제 연산
MinHeap의 삭제 연산은 다음과 같은 단계로 이루어진다.
1.
Heap에서 가장 작은 값을 가진 노드(루트 노드)를 제거한다.
2.
Heap의 맨 마지막에 있는 노드를 루트 노드로 이동시킨다.
3.
새로운 루트 노드와 자식 노드의 값을 비교하여, 자식 노드의 값이 작다면 루트 노드의 위치를 교환한다.
4.
이전 단계에서 교환된 새로운 루트 노드와 자식 노드의 값 비교를 반복한다.
heappop() {
if (this.size() === 0) return 0;
if (this.size() === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.heapifyDown();
return min;
}
heapifyDown() {
let index = 0;
while(this.getLeftChildIndex(index) < this.size()) {
let smallerChildIndex = this.getLeftChildIndex(index);
const rightChildIndex = this.getRightChildIndex(index);
if (
rightChildIndex < this.size() &&
this.heap[rightChildIndex] < this.heap[smallerChildIndex]
) {
smallerChildIndex = rightChildIndex;
}
if (this.heap[index] <= this.heap[smallerChildIndex]) break;
this.swap(index, smallerChildIndex);
index = smallerChildIndex;
}
}
JavaScript
복사
입력 & 출력
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`;
let input = fs.readFileSync(filePath).toString().trim().split('\n').map(Number);
N = input[0];
commands = input.slice(1);
let answer = '';
const heap = new MinHeap();
for (c of commands) {
if (c === 0) {
answer += heap.heappop() + '\n';
} else {
heap.heappush(c);
}
}
console.log(answer);
JavaScript
복사
출력을 할 때 주의할 점은 heappop()을 함과 동시에 console.log로 출력을 하게 될 경우 시간 초과가 난다는 점이다. 따라서, heappop() 결과를 바로 출력하지 말고 문자열에 누적한 뒤, 한 번에 출력해야 시간 초과를 피할 수 있다.
풀이 코드
class MinHeap {
constructor() {
this.heap = [];
}
getParentIndex(index) {
return Math.floor((index - 1) / 2);
}
getLeftChildIndex(index) {
return 2 * index + 1;
}
getRightChildIndex(index) {
return 2 * index + 2;
}
size() {
return this.heap.length;
}
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
heappush(value) {
this.heap.push(value);
this.heapifyUp();
}
heapifyUp() {
let index = this.size() - 1;
while(index > 0 && this.heap[this.getParentIndex(index)] > this.heap[index]) {
this.swap(index, this.getParentIndex(index));
index = this.getParentIndex(index);
}
}
heappop() {
if (this.size() === 0) return 0;
if (this.size() === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.heapifyDown();
return min;
}
heapifyDown() {
let index = 0;
while(this.getLeftChildIndex(index) < this.size()) {
let smallerChildIndex = this.getLeftChildIndex(index);
const rightChildIndex = this.getRightChildIndex(index);
if (
rightChildIndex < this.size() &&
this.heap[rightChildIndex] < this.heap[smallerChildIndex]
) {
smallerChildIndex = rightChildIndex;
}
if (this.heap[index] <= this.heap[smallerChildIndex]) break;
this.swap(index, smallerChildIndex);
index = smallerChildIndex;
}
}
}
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`;
let input = fs.readFileSync(filePath).toString().trim().split('\n').map(Number);
N = input[0];
commands = input.slice(1);
let answer = '';
const heap = new MinHeap();
for (c of commands) {
if (c === 0) {
answer += heap.heappop() + '\n';
} else {
heap.heappush(c);
}
}
console.log(answer);
JavaScript
복사
