![](https://velog.velcdn.com/images/hugh0223/post/a3281929-a84f-4367-8495-2555b234319d/image.png)
🖋️ 프로그래머스 힙 (HEAP)
@ 더 맵게
- 모든 음식의 스코빌 지수를 K 이상으로 만들기위한
섞어야 하는 최소 횟수
- 스코빌 지수가 가장 낮은 두 개의 음식을 특별한 방법으로 섞어 새로운 음식 만들기
- 섞은 음식의 스코빌 지수 = 가장 낮은 스코빌 지수 + (두 번째 낮은 스코빌 지수 * 2)
- 스코빌 지수를 담은 배열 scoville
- 원하는 스코빌 지수 K
class MinHeap {
constructor() {
this.heap = [];
}
size() {
return this.heap.length;
}
peek() {
return this.heap[0];
}
push(value) {
this.heap.push(value);
let currentIndex = this.heap.length - 1;
while (
currentIndex > 0 &&
this.heap[currentIndex] < this.heap[Math.floor((currentIndex - 1) / 2)]
) {
const temp = this.heap[currentIndex];
this.heap[currentIndex] = this.heap[Math.floor((currentIndex - 1) / 2)];
this.heap[Math.floor((currentIndex - 1) / 2)] = temp;
currentIndex = Math.floor((currentIndex - 1) / 2);
}
}
pop() {
if (this.heap.length === 0) return null;
else if (this.heap.length === 1) return this.heap.pop();
const minValue = this.heap[0];
this.heap[0] = this.heap.pop();
let currentIndex = 0;
while (currentIndex * 2 + 1 < this.heap.length) {
let minChildIndex = currentIndex * 2 + 2 < this.heap.length && this.heap[currentIndex * 2 + 2] < this.heap[currentIndex * 2 + 1] ? currentIndex * 2 + 2 : currentIndex * 2 + 1;
if (this.heap[currentIndex] < this.heap[minChildIndex]) {
break;
}
const temp = this.heap[currentIndex];
this.heap[currentIndex] = this.heap[minChildIndex];
this.heap[minChildIndex] = temp;
currentIndex = minChildIndex;
}
return minValue;
}
}
function solution(scoville, K) {
const minHeap = new MinHeap();
for (const sco of scoville) minHeap.push(sco);
let mixedCnt = 0;
while(minHeap.size() >= 2 && minHeap.peek() < K){
const first = minHeap.pop();
const second = minHeap.pop();
const mixedFood = first + second * 2;
minHeap.push(mixedFood);
mixedCnt++;
}
return minHeap.peek() >= K ? mixedCnt : -1;
}
@ 디스크 컨트롤러
- 한 번에 하나의 작업만 수행
- 가장 일반적인 방법은 요청이 들어온 순서대로 처리
- 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리
각 작업의 요청부터 종료까지 걸린 시간의 평균
- [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs
- (단, 소수점 이하의 수는 버립니다)
function solution(jobs) {
const count = jobs.length;
const minHeap = new MinHeap();
jobs.sort((a,b) => a[0]-b[0]);
let time = 0;
let complete = 0;
let total = 0;
while(jobs.length || minHeap.size()) {
while(jobs.length) {
if(jobs[0][0] === time) {
minHeap.push(jobs.shift());
} else break;
}
if(minHeap.size() && time >= complete) {
const task = minHeap.pop();
complete = task[1] + time;
total += complete - task[0];
}
time++;
}
return total / count >> 0;
}
class MinHeap {
constructor() {
this.heap = [ null ];
}
size() {
return this.heap.length - 1;
}
getMin() {
return this.heap[1] ? this.heap[1] : null;
}
swap(a, b) {
[ this.heap[a], this.heap[b] ] = [ this.heap[b], this.heap[a] ];
}
push(value) {
this.heap.push(value);
let curIdx = this.heap.length - 1;
let parIdx = (curIdx / 2) >> 0;
while(curIdx > 1 && this.heap[parIdx][1] > this.heap[curIdx][1]) {
this.swap(parIdx, curIdx)
curIdx = parIdx;
parIdx = (curIdx / 2) >> 0;
}
}
pop() {
const min = this.heap[1];
if(this.heap.length <= 2) this.heap = [ null ];
else this.heap[1] = this.heap.pop();
let curIdx = 1;
let leftIdx = curIdx * 2;
let rightIdx = curIdx * 2 + 1;
if(!this.heap[leftIdx]) return min;
if(!this.heap[rightIdx]) {
if(this.heap[leftIdx][1] < this.heap[curIdx][1]) {
this.swap(leftIdx, curIdx);
}
return min;
}
while(this.heap[leftIdx][1] < this.heap[curIdx][1] || this.heap[rightIdx][1] < this.heap[curIdx][1]) {
const minIdx = this.heap[leftIdx][1] > this.heap[rightIdx][1] ? rightIdx : leftIdx;
this.swap(minIdx, curIdx);
curIdx = minIdx;
leftIdx = curIdx * 2;
rightIdx = curIdx * 2 + 1;
if(leftIdx >= this.size()) break;
}
return min;
}
}
function solution(jobs) {
jobs.sort(([a, b], [c, d]) => a - c || b - d);
const waiting = [];
const count = jobs.length;
let processed_time = 0;
let time = 0;
while (jobs.length + waiting.length) {
let in_process;
while (jobs.length && (jobs[0][0] <= time)) {
waiting.push(jobs[0] && jobs.shift());
}
if (waiting.length) {
in_process = waiting.sort(([a, b], [c, d]) => b - d || a - c).shift();
} else {
in_process = jobs.shift();
time = in_process[0];
}
time += in_process[1];
processed_time += time - in_process[0];
}
return Math.floor(processed_time / count);
}