23.04.25. 풀었던 문제들

Leetcode 2336. Smallest Number in Infinite Set

 2개의 값으로 쉽게 풀 수 있다. 처음에는 pq로 두었는데... 이렇게 두면 이미 addBack한 숫자를 또 addBack하는 경우 중복이 발생하는데 이를 해결하지 못한다. 따라서 set으로 해결했다.

 

• infinite set에서 제일 작은 숫자인 start 변수, 그리고 infinite에 있지 않은, popSmallest() 한 이후에 addBack()된 숫자들을 저장하는 목록 s을 둔다.
• popSmallest()의 경우, s에 값이 있는 경우 무조건 start보다 작은 수가 s에 들어가 있는 것이므로 s에서 제일 작은 숫자를 pop하고 그것을 리턴한다. 그렇지 않다면 start값을 리턴하고, start++한다.
• addBack()의 경우에는, 주어진 num이 start보다 크거나 같다면 해당 숫자는 이미 infinite set에 있는 것이므로 아무것도 하지 않는다. 그렇지 않다면 s에 넣어 주어야 한다.

// Runtime 73 ms Beats 91.65%
// Memory 35.4 MB Beats 84.48%

class SmallestInfiniteSet {
public:
    int start;
    set<int> s;
    SmallestInfiniteSet() {
        start = 1;
    }

    // start는 infinite의 시작 숫자, pq는 addBack()했을 때 infinite에 있지 않을 때 들어가는 공간
    
    int popSmallest() {
        if(!s.empty()){
            int top = *s.begin(); s.erase(s.begin());
            return top;
        }
        start++;
        return start-1;
    }
    
    void addBack(int num) {
        if(num < start) s.insert(num);
    }
};`

 

시간복잡도

 popSmallest는 s에서 pop하므로 logn, addBack은 insert하므로 logn이다. 따라서 n개의 명령어가 주어질 때 O(nlogn)이다.

 

공간복잡도

 set에는 worst case O(n)의 정수가 들어갈 것이다. 따라서 O(n)