🎯 목표

Priority Queue(우선순위 큐)를 min heap으로 구현
프로그래머스 문제 더 맵게 풀기

(1)포스팅에 이어집니다.

🔒 문제 : 더 맵게(LEVEL 2)

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이다.

🔧 Priority Queue 를 min heap 구조로 설계하기

min heap을 이용해 어떤식으로 계산할 지 먼저 생각해봐야 한다.

1. 배열을 재배열하기(rearrange)

• heapify
• 혹은 모든 요소를 순회하여 insert하기

2. 첫 번째 요소와 두 번째 요소 선택해오기
3. 섞은 후
   1. K이상이면 재배열 하기
   2. K이하면 다시 순회
4. 만약 모든 숫자가 섞어도 K이상을 넘지 못하면 -1 반환

💻 코드로 구현하기

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 // 가장 작은 값 반환
    }
}

🎉 채점 결과

효율성 테스트 시 조금 느리게 나온 것 같은데 어느 부분에서 시간이 걸리는지
생각을 해봐야할 것 같다.