2336. Smallest Number in infinite Set

문제

https://leetcode.com/problems/smallest-number-in-infinite-set/description/

풀이

class SmallestInfiniteSet {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    Set<Integer> set = new HashSet<>();
    int n = 1;

    public SmallestInfiniteSet() {
        set.add(1);
        heap.add(1);
    }
    
    public int popSmallest() {
        int x = heap.poll();
        set.remove(x);
        heap.add(++n);
        set.add(n);

        return x;
    }
    
    public void addBack(int num) {
        if(n > num && !set.contains(num)) {
            heap.add(num);
            set.add(num);
        }
    }
}

• infinite한 set을 만들기에는 무리가 있음 -> infinite한 것 같은 유한한 set만들기
• set을 이용해 O(1)로 존재하는지 빠르게 확인, 존재하지 않는다면 n보다 작을 때 heap과 set에 추가
  • n보다 작은데 set에 없어야 그 전에 pop된 이력이 있는 것

class SmallestInfiniteSet {
    PriorityQueue<Integer> heap;
    Set<Integer> set;
    int n;

    public SmallestInfiniteSet() {
        n = 1;
        heap = new PriorityQueue<>();
        set = new HashSet<>();
    }
    
    public int popSmallest() {
        if(!heap.isEmpty()) {
            int x = heap.poll();
            set.remove(x);
             return x;
        }
        return n++;
    }
    
    public void addBack(int num) {
        if(n > num && !set.contains(num)) {
            heap.add(num);
            set.add(num);
        }
    }
}

• 시간 개선. 굳이 heap에 매번 n을 넣어줄 필요가 없음