최소 힙
문제 설명
최소 힙을 이용한 가장 간단한 문제였다.
입력 첫줄에 연산의 갯수 N이 주어지고 그 다음줄부터는 연산이 들어온다.
그런데 여기서 0 이 들어올 경우 최소 힙에서 최상단 값을 가져오는 연산이고 그 외의 자연수는 모두 힙에 추가하는 연산이다.
풀이 과정
- 힙 구현
insert(element)는 힙의 마지막 값에element를 넣고 반복문을 통해 비교하며 정렬remove()는 최상단 값을 제거, 힙의 마지막 값을 최상단에 넣고 자식 노드와 비교하면 정렬
- 힙을 이용하여 반복문을 돌며 명령 시행
MinHeap 구현 코드
class MinHeap {
constructor() {
this.heap = [null];
}
insert(element) {
let current = this.heap.length;
// 마지막 노드부터 부모노드로 가며 비교
while (current > 1) {
const parent = Math.floor(current / 2);
if (this.heap[parent] > element) {
this.heap[current] = this.heap[parent];
current = parent;
}else break; // 만약 부모 노드가 더 작으면 반복문 탈출
}
this.heap[current] = element;
}
remove() {
let top = this.heap[1];
if (this.heap.length > 2) {
this.heap[1] = this.heap[this.heap.length - 1];
this.heap.splice(this.heap.length - 1);
let current = 1;
let leftChild = current * 2;
let rightChild = current * 2 + 1;
// 자식 노드를 비교
while (this.heap[leftChild]) {
let CompareChild = leftChild;
//왼쪽 자식과 오른쪽 자식을 비교
if (this.heap[rightChild] && this.heap[leftChild] > this.heap[rightChild]) {
CompareChild = rightChild;
}
// 자식 노드와 부모 노드 비교 , 구조분해 할당으로 교체
if (this.heap[CompareChild] < this.heap[current]) {
[this.heap[CompareChild], this.heap[current]] = [this.heap[current], this.heap[CompareChild]];
current = CompareChild;
}else break;
leftChild = current * 2;
rightChild = current * 2 + 1;
}
}else if (this.heap.length === 2) {
this.heap.splice(1, 1);
}else{
return 0;
}
return top;
}
getSize() {
return this.heap.length - 1;
}
}전체 코드
let fs = require("fs");
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\n").map(Number);
let N = input.shift();
class MinHeap {
constructor() {
this.heap = [null];
}
insert(element) {
let current = this.heap.length;
while (current > 1) {
const parent = Math.floor(current / 2);
if (this.heap[parent] > element) {
this.heap[current] = this.heap[parent];
current = parent;
}else break;
}
this.heap[current] = element;
}
remove() {
let top = this.heap[1];
if (this.heap.length > 2) {
this.heap[1] = this.heap[this.heap.length - 1];
this.heap.splice(this.heap.length - 1);
let current = 1;
let leftChild = current * 2;
let rightChild = current * 2 + 1;
while (this.heap[leftChild]) {
let CompareChild = leftChild;
if (this.heap[rightChild] && this.heap[leftChild] > this.heap[rightChild]) {
CompareChild = rightChild;
}
if (this.heap[CompareChild] < this.heap[current]) {
[this.heap[CompareChild], this.heap[current]] = [this.heap[current], this.heap[CompareChild]];
current = CompareChild;
}else break;
leftChild = current * 2;
rightChild = current * 2 + 1;
}
}else if (this.heap.length === 2) {
this.heap.splice(1, 1);
}else{
return 0;
}
return top;
}
getSize() {
return this.heap.length - 1;
}
}
const PQ = new MinHeap();
for (const Order of input) {
if (Order === 0) {
console.log(PQ.remove());
} else {
PQ.insert(Order);
}
}
그런데 여기서 시간초과 가 발생했다.
무엇이 원인일까?
하나씩 코드를 뜯어보기 시작했다.
Minheap내부에서splice()를 이용하여 배열을 수정했는데splice()대신pop()을 사용해야하나 ?- 참고)
splice()는 시간 복잡도가 O(n) 이고 pop은 O(1) 이다.
- 참고)
- 구조분해 할당이 시간 초과를 발생하게 하나 ?
- 정확히 어디서 봤는지 기억이 안나는데 백준에서 구조분해 할당이
tmp변수를 임시로 이용하는 것보다 시간이 걸린다는 글을 봤다.
- 정확히 어디서 봤는지 기억이 안나는데 백준에서 구조분해 할당이
console.log를 너무 많이 써서 그런가 ?
정답은 바로 console.log 때문이었다.
매번 console.log로 출력을 하는것이 시간 초과를 발생시켰던 것이다.
그래서 바로 수정을 진행했고 앞서 말한 모든 것들을 수정한 코드는 다음과 같다
수정 코드
let fs = require("fs");
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\n").map(Number);
let N = input.shift();
class MinHeap {
constructor() {
this.heap = [null];
}
insert(element) {
let current = this.heap.length;
while (current > 1) {
const parent = Math.floor(current / 2);
if (this.heap[parent] > element) {
this.heap[current] = this.heap[parent];
current = parent;
}else break;
}
this.heap[current] = element;
}
remove() {
let top = this.heap[1];
if (this.heap.length > 2) {
this.heap[1] = this.heap.pop();
let current = 1;
let leftChild = current * 2;
let rightChild = current * 2 + 1;
while (this.heap[leftChild]) {
let CompareChild = leftChild;
if (this.heap[rightChild] && this.heap[leftChild] > this.heap[rightChild]) {
CompareChild = rightChild;
}
if (this.heap[CompareChild] < this.heap[current]) {
const temp = this.heap[current];
this.heap[current] = this.heap[CompareChild];
this.heap[CompareChild] = temp;
current = CompareChild;
}else break;
leftChild = current * 2;
rightChild = current * 2 + 1;
}
}else if (this.heap.length === 2) {
this.heap.pop();
}else{
return 0;
}
return top;
}
getSize() {
return this.heap.length - 1;
}
}
let answer = '';
const PQ = new MinHeap();
for (const Order of input) {
if (Order === 0) {
answer += `${PQ.remove()}\n`;
} else {
PQ.insert(Order);
}
}
console.log(answer);
후기
console.log 가 매우 느리다는 사실을 알게 되었고 다음부터는 애초에 문자열을 만들어서 출력을 진행하는 방법으로 풀이를 진행해야겠다.
JavaScript를 사용하는 모두를 위해...