LeetCode - 2336. Smallest Number in Infinite Set (Java)

문제: 2336. Smallest Number in Infinite Set (Medium)

 

1. 모든 양의 정수를 포함하는 집합이 있음.
2. SmallestInfiniteSet Class 를 구현.
    1) SmallestInfiniteSet() : 모든 양의 정수를 초기화.
    2) int popSmallest() : 집합에서 가장 작은 정수를 삭제하고 리턴.
    3) void addBack(int num): 집합에 num 값이 존재하지 않다면, 다시 집합에 num 정수를 추가.

 

 

 

풀이:

class SmallestInfiniteSet {

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

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

 

설명: 

 

1. 모든 양의 정수를 정의해 놓는 것 보다 전부 있다고 가정하고 처리하는 것이 낫겠다고 판단하여 가장 작은 정수를 기록할 cursor 변수와 cursor 보다 작은 정수를 기록할 PriorityQueue 를 선언.

2. SmallestInfiniteSet() 에서 PriorityQueue 초기화.

3. popSmallest() 에서 PriorityQueue 에 값이 존재할 경우, cursor 보다 작고 이미 지워졌던 값이므로 PriorityQueue 에서 값 제거 후 리턴, 아닐 경우 cursor 를 리턴하고 값 증가. 

4. addBack(int num) 에서 num 이 cursor 보다 작고 PriorityQueue 에 값이 존재하지 않을 경우 PriorityQueue 에 값 추가.

 

 

Runtime: 8ms Beats 99.95% of users with Java

Memory: 44.83MB Beats 5.58% of users with Java

 

 

---

개인의 해답으로 풀이한 문제입니다. 
절대적인 정답이 아닐 수 있으며, 더 좋은 개선 방안이 있다면 댓글로 의견 주세요.