99클럽 코테 스터디 4일차 TIL, Heap(Smallest Number in Infinite Set)

1. 문제 정의

 

2. 문제 접근

PriorityQueue를 써서 마지막 인덱스를 기억했다가 계속해서 활용해주면 될 것 같다.

3. 문제 풀이

1. PriorityQueue 를 이용하여 마지막 인덱스를 기억한다.
2. 조건에 맞으면 숫자를 넣어준다.
3. pop을 할때 pq가 비었으면 마지막인덱스를 리턴하고, 아니면 pq의 내용을 pop해준다.

4. 코드

class SmallestInfiniteSet {

    PriorityQueue<Integer> pq;
    int lowerIdx = 1;

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

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

 

5. 회고

처음에는 Stack을 썼었는데 그러면 뽑아내는 순서가 순서대로 나오지 않는다. PriorityQueue 를 쓸 경우 자동으로 오름차순으로 안에서 정렬을 해주기 때문에 편하다.