[JS] 더 맵게!

생각보다 되게 오래 헤맨 문제였다... 원인은 별거 아니었지만

 

 

우선 문제분류도 그렇고 내용도 그렇고 내놓고 최소힙을 구현해보란 문제였다. 딱히 최대,최소 힙 라이브러리가 없는 JS 특성상 힙을 직접 구현해보았다.

 

내가 실수한점은 두곳이었다.

 

첫번째로 문제를 제대로 안읽은 게 잘못이었다. 스코빌 지수가 다 섞어도 원하는 스코빌 지수가 안나오는 경우가 있는데 해당 경우를 다 무시해버렸었다..

 

추가적으로 스코빌 이상인지 초과인지 제대로 파악을 안했어서 테스트 케이스가 잘 통과가 안되었었다.

 

 

문제를 파악을 제대로 못했는데 애꿏은 힙부분만 계속 건드렸으니 ㅠㅠ

 

힙 부분에서 실수한 곳은 한 점이었다.

 

 

 

[1,1] , 3 이렇게 테스트 케이스를 넣으면 답이 정상적으로 나오지 않았다.

 

 

힙 안의 값이 1개밖에 없다면 그냥 pop을 해주면 되는데 그 처리를 안해준 것이 잘못이었다.

 

 

 

 

 

class MinHeap {
    
    constructor() {
        this.ary = [0]
        this.size = 0
    }
    
    swap(a,b) {
        [this.ary[a],this.ary[b]] = [this.ary[b],this.ary[a]]
    }
    
    push(value) {
        this.ary.push(value)
        let idx = ++this.size
        
        while (idx>0 && this.ary[idx] <= this.ary[~~(idx/2)]){
            this.swap(idx,~~(idx/2))
            idx = ~~(idx/2)
        }
    }
    
   pop() {
        if (this.size == 1) {
            this.size --
            return this.ary.pop()
        }
        const ret = this.ary[1]
        this.ary[1] = this.ary.pop()
        let idx = 1
        this.size-=1
       
        while (idx*2 <= this.size) {
             const [left,right] = [idx*2,idx*2+1]
             let minIdx = left
             if (right <= this.size && this.ary[right] < this.ary[left]) minIdx = right
             
             if (this.ary[minIdx] < this.ary[idx]){
                 this.swap(idx,minIdx)
                 idx = minIdx
             } else break
        }
            return ret
        }
    get() {
        return this.ary[1]
    }
    
}


function solution(scoville, K) {
    const heap = new MinHeap()
    
    for (const food of scoville) {
        heap.push(food)
    }
    
    
    let ret = 0
    
    while (heap.get() < K) {
        if (heap.size <= 1) return -1; // 예외 처리: 스코빌 지수를 만들 수 없는 경우
        heap.push(heap.pop() + heap.pop() * 2)
        ret +=1
    }
    
    return ret
}