[LeetCode] 1046. Last Stone Weight

😎풀이

1. 최대 힙 구현
2. stones를 순회하며 힙에 입력
3. 힙 요소를 하나씩 빼며 충돌 후 잔여 값 다시 입력
4. 최종 값 반환

class MaxHeap {
    private arr: number[]
    constructor() {
        this.arr = []
    }
    pop() {
        if (this.arr.length === 0) return 0;
        if (this.arr.length === 1) return this.arr.pop();
        
        const val = this.arr[0];
        this.arr[0] = this.arr.pop();
        this.heapifyDown(0);
        return val;
    }
    push(num: number) {
        this.arr.push(num)
        this.heapifyUp(this.arr.length - 1)
    }
    heapifyUp(idx: number) {
        const parentIdx = Math.floor((idx - 1) / 2)
        if(idx <= 0 || this.arr[parentIdx] >= this.arr[idx]) return
        [this.arr[idx], this.arr[parentIdx]] = [this.arr[parentIdx], this.arr[idx]]
        this.heapifyUp(parentIdx)
    }
    heapifyDown(idx: number) {
        const leftIdx = idx * 2 + 1
        const rightIdx = idx * 2 + 2
        let largest = idx;

        if (leftIdx < this.arr.length && this.arr[leftIdx] > this.arr[largest]) {
            largest = leftIdx;
        }

        if (rightIdx < this.arr.length && this.arr[rightIdx] > this.arr[largest]) {
            largest = rightIdx;
        }

        if (largest !== idx) {
            [this.arr[idx], this.arr[largest]] = [this.arr[largest], this.arr[idx]];
            this.heapifyDown(largest);
        }
    }
    size() {
        return this.arr.length
    }
}

function lastStoneWeight(stones: number[]): number {
    const stoneHeap = new MaxHeap()
    for(const stone of stones) stoneHeap.push(stone)
    while(stoneHeap.size() > 1) {
        const first = stoneHeap.pop()
        const second = stoneHeap.pop()
        const crashed = Math.abs(first - second)
        if(crashed > 0) stoneHeap.push(crashed)
    }
    return stoneHeap.pop() ?? 0
};