[LeetCode] 2336. Smallest Number in Infinite Set, Medium

1. 문제

• 조건을 만족하는 SmallestInfiniteSet 클래스를 구현하라.
  • 생성 시 모든 양수를 담아 초기화 한다.
  • popSmallest() : 가장 작은 수를 반환한다.
  • addBack(int num): 입력 받은 정수가 없는 경우, 해당 값을 삽입한다.

2. 해결

class MinHeap {
    private heap: number[];

    constructor() {
        this.heap = [];
    }

    getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
    getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
    getParentIndex = (childIndex) => Math.floor((childIndex - 1) /2);

    swap = (i: number, j: number) => {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    };

    peek = () => this.heap[0];
    size = () => this.heap.length;

    push(value: number) {
        this.heap.push(value);
        this.heapifyUp();
    }

    heapifyUp() {
        let index = this.heap.length - 1; // 마지막 요소.

        while(index > 0 && this.heap[this.getParentIndex(index)] > this.heap[index]) { // 부모 노드보다 자식 노드가 작은 경우.
            this.swap(index, this.getParentIndex(index)); // 스왑.
            index = this.getParentIndex(index);
        }
    }

    pop(): number | undefined {
        if(this.heap.length === 0) return undefined;
        if(this.heap.length === 1) return this.heap.pop();

        const top = this.heap[0];
        this.heap[0] = this.heap.pop(); // 마지막 값을 root로 놓고.
        this.heapifyDown();

        return top;
    }

    heapifyDown() {
        let index = 0;
        
        while(this.getLeftChildIndex(index) < this.heap.length) { // 자식이 있는 경우 반복, left가 없으면 right도 없기 때문에.
            // 왼쪽, 오른쪽 중 더 작은 자식을 찾음. 최소 힙이므로.
            let smallerChildIndex = this.getLeftChildIndex(index);
            const rightChildIndex = this.getRightChildIndex(index);

            if(rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[smallerChildIndex]) {
                smallerChildIndex = rightChildIndex;
            }

            if(this.heap[index] <= this.heap[smallerChildIndex]) break; // 현재 노드가 자식보다 작거나 같으면 종료.

            this.swap(index, smallerChildIndex);
            index = smallerChildIndex;
        }
    }
}

class SmallestInfiniteSet {
    heap: MinHeap;
    set: Set<number>;
    constructor() {
        this.heap = new MinHeap();
        this.set = new Set<number>();

        for(let i = 1; i < 1001; i++) {
            this.heap.push(i);
            this.set.add(i);
        }
    }

    popSmallest(): number {
        const num = this.heap.pop();
        if(num) {
            this.set.delete(num);
            return num;
        }
    }

    addBack(num: number): void {
        if(!this.set.has(num)) {
            this.heap.push(num);
            this.set.add(num);
        }
    }
}

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * var obj = new SmallestInfiniteSet()
 * var param_1 = obj.popSmallest()
 * obj.addBack(num)
 */

• 최소 힙과 Set을 활용한다.