[백준, 실버2, JS] 최소 힙
문제
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
배열에 자연수 x를 넣는다.
배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.
입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.내 풀이
const [n, ...arr] = require('fs')
.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
.toString()
.trim()
.split('\n');
class MinHeap {
constructor() {
this.value = [];
}
getIdx() {
return this.value.length - 1;
}
enqueue(el) {
this.value.push(el);
this.bubbleUp();
}
dequeue() {
const min = this.value[0];
if (!this.getIdx()) return this.value.shift();
this.value[0] = this.value.pop();
this.bubbleDown();
return min;
}
bubbleUp() {
let childNodeIdx = this.getIdx();
while (childNodeIdx) {
const parentNodeIdx = Math.floor((childNodeIdx - 1) / 2);
const childNode = this.value[childNodeIdx];
const parentNode = this.value[parentNodeIdx];
if (childNode < parentNode) {
this.value[childNodeIdx] = parentNode;
this.value[parentNodeIdx] = childNode;
childNodeIdx = parentNodeIdx;
continue;
}
break;
}
}
bubbleDown() {
const maxIdx = this.getIdx();
let idx = 0;
while (maxIdx && idx <= maxIdx) {
let swapIdx = null;
const parentNode = this.value[idx];
const leftChildIdx = idx * 2 + 1;
const leftChild = this.value[leftChildIdx];
if (leftChild && leftChild < parentNode) {
swapIdx = leftChildIdx;
}
const rightChildIdx = idx * 2 + 2;
const rightChild = this.value[rightChildIdx];
if (
(!swapIdx && rightChild < parentNode) ||
(swapIdx && rightChild < leftChild)
) {
swapIdx = rightChildIdx;
}
if (swapIdx === null) break;
this.swap(idx, swapIdx);
idx = swapIdx;
}
}
swap(parentIdx, childIdx) {
const parentNode = this.value[parentIdx];
const childNode = this.value[childIdx];
this.value[parentIdx] = childNode;
this.value[childIdx] = parentNode;
}
}
const minHeap = new MinHeap();
let result = '';
arr.forEach((el) => {
if (!+el) {
if (!minHeap.value.length) return result += '0\n'
const min = minHeap.dequeue();
result += `${min}\n`
return;
}
minHeap.enqueue(+el);
});
console.log(result)배운 점
드디어 힙 정렬을 이해했다
자바스크립트는 힙 구조를 만들어줘야 해서 귀찮긴 하지만
문제를 풀면서 계속 구현하면 나중에는 빨리 구현할 수 있지 않을까 싶다
[Lv2, 58%, JS] 더 맵게
문제
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.내 답
class MinHeap {
constructor() {
this.arr = [];
}
getLen() {
return this.arr.length;
}
enqueue(el) {
if (!el) return;
this.arr.push(el);
this.bubbleUp();
this.sinkDown();
}
dequeue() {
const min = this.arr[0];
const end = this.arr.pop();
if(this.arr.length) {
this.arr[0] = end;
this.sinkDown();
}
return min;
}
bubbleUp() {
let len = this.getLen() - 1;
while (true) {
if (!len) return;
const parLen = Math.floor((len - 1) / 2);
const parNum = this.arr[parLen];
const childNum = this.arr[len];
if (this.arr[len] >= this.arr[parLen]) break;
this.arr[len] = parNum;
this.arr[parLen] = childNum;
len = parLen;
}
}
sinkDown() {
let idx = 0;
const len = this.getLen();
const target = this.arr[0];
while (true) {
const leftChildIdx = 2 * idx + 1;
const rightChildIdx = 2 * idx + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIdx < len) {
leftChild = this.arr[leftChildIdx];
if (leftChild < target) {
swap = leftChildIdx;
}
}
if (rightChildIdx < len) {
rightChild = this.arr[rightChildIdx];
if (
(rightChild < target && !swap) ||
(rightChild < leftChild && swap)
) {
swap = rightChildIdx;
}
}
if (!swap) break;
this.arr[idx] = this.arr[swap];
this.arr[swap] = target;
idx = swap;
}
}
}
function solution(scoville, K) {
const minHeap = new MinHeap();
scoville.forEach((el) => {
minHeap.enqueue(el);
});
let cnt = 0;
while (true) {
if (!minHeap.arr.length) break;
if (minHeap.arr[0] >= K) break;
const min = minHeap.dequeue();
const second = minHeap.dequeue();
const newNode = second * 2 + min;
minHeap.enqueue(newNode);
cnt += 1;
}
if(minHeap.arr[0] < K || !minHeap.arr.length) return -1
return cnt;
}배운 점
처음 풀었던 힙 문제
힙 구조를 배우면서 처음으로 구현했던 힙 구조이다.
이찬