[ leetcode ] 2336. Smallest Number in Infinite Set

무한한 set이 있고, 해당 set에는 모든 자연수가 포함되어 있습니다. 아래 함수들을 구현하여 입력된 명령어 후 남은 자연수들을 반환하는 문제입니다.

 

You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].
Implement the SmallestInfiniteSet class:

• SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.
• int popSmallest() Removes and returns the smallest integer contained in the infinite set.
• void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.

모든 수가 포함된 리스트를 준비할 수 없으니 다 포함되어 있다고 가정하고, pop된 set을 만들어 제거된 숫자만 관리하고 다시 추가될 경우 해당 set에서 제거하여 제거된 set에 없으면 존재하는 구조입니다.

그래서 set에서 count함수를 호출하여 0인 가장 작은 자연수를 popSmallest에서 반환합니다.

 

#include <set>

class SmallestInfiniteSet {
public:
    set<int> pop_list;

    SmallestInfiniteSet() {
        pop_list.clear();
    }
    
    int popSmallest() {
        int i = 1;
        for (; i <= 1000; i++) {
            if (pop_list.count(i) == 0) {
                break;
            }
        }
        pop_list.insert(i);
        return i;
    }
    
    void addBack(int num) {
        if (pop_list.count(num) > 0) pop_list.erase(num);
    }
};

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