[Heap/Priority Queue][Medium] 2336. Smallest Number in Infinite Set

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

Smallest Number in Infinite Set - LeetCode

 

Q. 모든 양의 정수를 포함하고 있는 컨테이너가 이미 존재한다. 

 이때 int popSmallest()를 호출하면, 그 수 중 가장 작은 수를 제거하고 반환한다.

 addBack(int num)을 하면 컨테이너에 존재하지 않을때, insert 한다.

 해당 작업을 하는 클래스를 작성하라. 

 

Solution. 

 이미 모든 수를 가지고 있고, 작은 순서대로 반환하면 된다. 따라서 값이 정렬되어 있어야 한다. 따라서 insert시 정렬이 자동 진행 되는 컨테이너가 필요하고, 

 또한 중복을 허용하지 않으므로, priority queue보다는 set, map 을 써야 할 것 같다.

  map은 두개의 키와 값, 두개의 input을 요구하지만, 여기서는 하나면 될 것 같다. 

  따라서 set 만 사용하기로 한다. 

 

class SmallestInfiniteSet 
{
    unsigned int mMin;	// 연속된 수의 최소 값.
    set<int> mSet;		// 위 min 보다 작은 수들의 컨테이너.
public:
    SmallestInfiniteSet() 
    {
        mMin = 1;		// 1부터 모든 양수를 다 가진다.
    }
    int popSmallest() 
    {
        if(mSet.size() > 0)
        {		
            // 이미 정렬된 가장 작은 수 반환.
            int ret = *mSet.begin();
            mSet.erase(ret);
            return ret;
        }
        ++mMin;
        return mMin - 1;
    }
    void addBack(int num) 
    {
        if (mMin > num)	// min 부터는 연속된 수 므로, 작은 수들 중 중복이 없으면 insert.
        {
            if (mSet.find(num) == mSet.end())
                mSet.insert(num);
        }
    }
};

 

 

결과.