Priority Queue(우선순위 큐)를 min heap으로 구현
프로그래머스 문제 더 맵게 풀기
(1)포스팅에 이어집니다.
Input
Scoville : 숫자로 된 배열
K : 스코빌 지수의 최소 값
Condition
섞은 음식의 Scoville = 가장 작은 Scoville + (두 번째로 작은 스코빌 * 2)
Output
매개변수 Scovile, K를 받아 K이상의 값만 가지도록 재 배열했을 때의 수
단, 위의 조건으로만 재배열 할 수 있음
예를들어, 아래와 같은 배열과 K값이 있다고 하자
const scovilleArr = [1, 2, 4, 6]
const K = 3
위의 조건을 부합하지 않는 요소는 [0]
번째 요소와 [1]
번째 요소다.
섞기 위해서는 1 + ( 1 * 2 ) = 3
이 되고 한 번만 섞으면 되므로 return 값은 1
이다.
min heap을 이용해 어떤식으로 계산할 지 먼저 생각해봐야 한다.
function solution(scoville, K) {
const minHeap = new MinHeap()
let mixedcount = 0;
for (const value of scoville) {
minHeap.insert(value)
}
while ( minHeap.peek(0) < K ) { // 가장 작은 값이 K보다 클 때까지 반복
const firstScoville = minHeap.delete()
const secondScoville = minHeap.delete()
const mix = firstScoville + secondScoville * 2 // 1st, 2nd숫자를 픽해서 넣어준 후
minHeap.insert(mix) // 섞은 값 배열에 추가
mixedcount ++ // 섞어주었으니 횟수 추가
}
return minHeap.peek(0) >= K ? mixedcount : -1;
}
class MinHeap {
constructor() {
this.heap = []
}
peek(n) {
return this.heap[n] // n번째로 작은 값
}
size() {
return this.heap.length - 1;
}
insert(value) {
this.heap.push(value)
if(this.heap.length === 1) { // 배열에 아무것도 없는 상태였다면
return // 값만 넣고 끝내기
}
// 부모노드를 찾은 뒤 부모노드와 비교하여 해당 값이 더 작으면 스와핑
let currentIdx = this.size()
let parentIdx = Math.floor((currentIdx - 1) / 2)
while ( currentIdx > 0 && this.heap[currentIdx] < this.heap[parentIdx] ) {
// while문 사용 : 해당 값이 이 조건에 부합하지 않을때까지 반복
[this.heap[currentIdx], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[currentIdx]]
// 구조분해 할당을 이용하여 값을 바꿔줌
currentIdx = parentIdx
parentIdx = Math.floor((currentIdx - 1) / 2 )
// 값을 바꿔주었으니 index값도 변경해줌
}
}
delete() {
const smallestValue = this.heap[0]
const biggestValue = this.heap.pop()
if(this.heap.length > 0) {
this.heap[0] = biggestValue;
let currentIdx = 0
while(
this.heap[currentIdx] > this.heap[currentIdx * 2 + 1] ||
this.heap[currentIdx] > this.heap[currentIdx * 2 + 2]
) {
let smallerChildIdx =
this.heap[currentIdx * 2 + 1] > this.heap[currentIdx * 2 + 2]
? currentIdx * 2 + 2 : currentIdx * 2 + 1
// 더 작은 자식노드와 현재 값을 스와핑
// 임시 변수를 사용하여 값 교환
let temp = this.heap[currentIdx]
this.heap[currentIdx] = this.heap[smallerChildIdx]
this.heap[smallerChildIdx] = temp
// 현재 인덱스를 업데이트
currentIdx = smallerChildIdx
}
}
return smallestValue // 가장 작은 값 반환
}
}
효율성 테스트 시 조금 느리게 나온 것 같은데 어느 부분에서 시간이 걸리는지
생각을 해봐야할 것 같다.