99클럽 코테 스터디 6일차 TIL - 2336. Smallest Number in Infinite Set (LeetCode)

 

오늘의 학습 키워드

• 우선순위큐

오늘의 회고

1. 문제

문제 URL

2. 해결 방안

import java.util.PriorityQueue;

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.add(num);
        }
    }
}

• 전체 정수를 초기화 하지 않고, 현재 최소값을 cursor 를 이용해 관리.
• addBack() : 큐에는 cursor 보다 작고, 큐에 포함되지 않은 값만 들어올 수 있다.
• popSmallest() : 큐에 있는 값이 cursor 보다 작기 때문에, 큐에 값이 존재한다면 큐에서 poll() 한다. 그게 아니면 cursor가 가장 작은 값이므로 커서 리턴 후 커서+1 처리.

3. 피드백

• 릿코드 코테는 첨 해봐서 영어라 어색어색열매..ㅠ 결과적으로 푸는 법 자체는 엄청 어렵지 않았는데 생각보다 떠올라지지않았다. hashset을 써야하나 싶었는데 우선순위큐로 해결할 수 있었음.

4. 새로 알게된 것

• PriorityQueue.contains(num) : 존재하는지 체크할 수 있는 메서드가 있다!
• + Collections 인 List, Queue, Hash 관련 객체에도 contains가 있구나! 유용할거같으니 꼭 기억하기~!!