[JS] 귤 고르기

Map 자료형에 값을 넣고 이를 개수에 대해 정렬한 다음 큰 값부터 우선적으로 빼내면 쉽게 해결할 수 있을 것 같은 문제였다.

 

 

근데 저번에 최대힙을 공부하기도 했고 힙을 빠르게 구현하는걸 연습 해볼겸 힙을 활용해서 문제를 풀어보았다.

 

정렬해서 큰값을 빼내는 부분을 Heap으로 대체해주었다.

 

 

 

다만.. 생각보다 신기한건 정렬을 활용해서 푼 문제와 생각처럼 시간이 많이 차이나지 않았고, 오히려 정렬이 더 빠른 경우가 많았다. 

물론 가장 테스트케이스가 큰 경우에는 Heap이 빠르기 했지만 실제로 테스트를 보는 입장이라면 heap구현은 시간이 많이 걸리므로 테스트 케이스의 개수를 잘 보아 가면서 사용해야 할 것 같다.

 

 

 

class Heap {
    constructor () {
        this.heap = [0]
        this.length = 0
    }
    
    getMax() {
        return this.heap[1] ? this.heap[1] : undefined
    }
    
    swap (a,b) {
        [this.heap[a],this.heap[b]] = [this.heap[b],this.heap[a]]
    }
    
    push(value) {
        this.heap.push(value)
        this.length += 1
        let idx = this.length
        while (idx > 1) {
            const parentIdx = ~~(idx/2)
            if (this.heap[parentIdx][1] < this.heap[idx][1]) {
                this.swap(parentIdx , idx)
                idx = parentIdx
            } else break
        }
    }
    
    pop() {
        if (!this.length) return undefined
        const max = this.heap[1]
        
        this.heap[1] = this.heap.pop()
        this.length --
        let idx = 1
        
        while (idx < this.length ){
            const [leftIdx,rightIdx] = [idx*2 , idx*2 + 1]
            
            let maxIdx = 1
            if (leftIdx > this.length) break
            else if (rightIdx > this.length) maxIdx = leftIdx
            else maxIdx = this.heap[leftIdx][1] > this.heap[rightIdx][1] ? leftIdx : rightIdx
            
            if (this.heap[idx][1] < this.heap[maxIdx][1]){
                this.swap(idx,maxIdx)
                idx = maxIdx
            } else break
        }
        return max
    }
}

function solution(k, tangerine) {
    const heap = new Heap()
    const map = new Map()
    for (const guel of tangerine){
        if (map.get(guel)) map.set(guel,map.get(guel) +1 )
        else map.set(guel,1)
    }
    for (const el of map) heap.push(el)
    
    let ret = 0
    let num = 0
    while (num < k) {
        num += heap.pop()[1]
        ret ++
    }
    
    return ret
    
}