[Heap / Priority Queue, Medium] Smallest Number in Infinite Set

https://leetcode.com/problems/smallest-number-in-infinite-set/description/?envType=study-plan-v2&envId=leetcode-75

문제가 특이하다.
일단 모든 양의 정수를 담아둘 수 있는 곳은 없기 때문에, 당연히 내부적으로는 특정 변수의 증감으로 표현해야 함 (next)

생성자
next 변수를 1로 초기화.
나중에 쓸 우선순위 큐도 미리 초기화.

addBack

• num이 next(지금까지 뽑은 수)보다 큼: 아무 의미없다. popSmallest는 어차피 가장 작은 수부터 뽑기 때문에 이 경우는 아예 아무 행동도 안 해도 됨
• num이 next보다 작음: 이미 한 번 뽑았던 수보다 작은 값을 다시 넣는다는 것이기 때문에 이 때 우선순위 큐가 필요함. 다만, 중복은 제거해야 함 (Set을 따로 쓰거나, 아니면 contains 메서드로 체크)

popSmallest

• 큐가 비어있지 않다면 큐에서 먼저 뽑음 (next보다 작기 때문에)
• 큐가 비어있다면 next를 반환하고 ++ 처리

class SmallestInfiniteSet {
    private int next;
    private PriorityQueue<Integer> pq;

    public SmallestInfiniteSet() {
        next = 1;
        pq = new PriorityQueue<>();
    }
    
    public int popSmallest() {
        if (!pq.isEmpty()) {
            return pq.poll();
        }
        return next++;
    }
    
    public void addBack(int num) {
        if (num < next && !pq.contains(num)) {
            pq.offer(num);
        }
    }
}