11279번: 최대 힙
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이
www.acmicpc.net
문제를 풀기 위해 가장 최대값을 먼저 pop해주는 큐를 구현해야한다.
템플릿으로 사용하기 위한 최대힙을 사용한 코드는 다음과 같다.
'use strict'
class MaxHeapTree {
values = []
isEmpty() {
return this.values.length === 0
}
parentIndexOf(index) {
return Math.floor((index - 1) / 2)
}
leftChildIndexOf(index) {
return index * 2 + 1
}
rightChildIndexOf(index) {
return index * 2 + 2
}
push(n) {
let index = this.values.length
this.values.push(n)
while (index !== 0) {
const parentIndex = this.parentIndexOf(index)
if (this.values[index] <= this.values[parentIndex]) {
break
} else {
this.swapValue(parentIndex, index)
index = parentIndex
}
}
}
pop() {
if (this.values.length === 1) {
return this.values.pop()
}
const retValue = this.values[0]
this.values[0] = this.values.pop()
let index = 0
while (index < this.values.length - 1) {
const leftChildIndex = this.leftChildIndexOf(index)
const rightChildIndex = this.rightChildIndexOf(index)
if (this.getValueOrMin(leftChildIndex) <= this.getValueOrMin(index) &&
this.getValueOrMin(rightChildIndex) <= this.getValueOrMin(index)) {
break
} else if (this.getValueOrMin(leftChildIndex) < this.getValueOrMin(rightChildIndex)) {
this.swapValue(index, rightChildIndex)
index = rightChildIndex
} else {
this.swapValue(index, leftChildIndex)
index = leftChildIndex
}
}
return retValue
}
swapValue(index1, index2) {
const tmp = this.values[index1]
this.values[index1] = this.values[index2]
this.values[index2] = tmp
}
getValueOrMin(idx) {
if (this.values.length <= idx) {
return -1
}
return this.values[idx]
}
}
const readline = require("readline");
const {
parse
} = require("path");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const solution = (input) => {
const q = new MaxHeapTree();
let answer = "";
input.forEach(element => {
element = parseInt(element);
if (element > 0) {
q.push(element);
} else {
if (q.isEmpty()) {
answer += "0\n";
} else {
answer += `${q.pop()}\n`;
}
}
});
console.log(answer);
};
const input = [];
rl.on("line", function (line) {
input.push(line);
}).on("close", function () {
solution(input.slice(1));
process.exit();
});
'개발 > Javascript' 카테고리의 다른 글
[Javascript] 내가 쓰려고 만든 자바스크립트 우선순위큐(Priority Queue)/Heap (0) | 2020.11.30 |
---|---|
[Javascript] 내가 쓰려고 만든 자바스크립트 코드 컨벤션 (0) | 2020.11.29 |
[Javascript] 우선순위 큐 활용하여 문제 풀기 (1927 최소힙) (0) | 2020.11.29 |
[Javascript] 자바스크립트의 "use strict"는 도대체 무엇일까? (0) | 2020.11.29 |
[Javascript] 자바스크립트 map() vs foreach() 비교하기 (0) | 2020.11.28 |