99클럽 코테 스터디 3일차 TIL : smallest-number-in-infinite-set (미들러)

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

문제 해석하는게 더 오래걸렸다,,, 영어공부 해야지

---

중복숫자를 허용하지 않는 min heap을 구현하는것과 비슷했다.

주어진 요구사항대로 동작하는 class SmallestInfiniteSet을 구현하면 되는 문제였다.

 

1. SmallestInfiniteSet()

    init을 통해 양의 정수를 무한대로 담고있는 smallestinfiniteset을 초기화한다.

    이 때, 문제에서 숫자의 범위를 1 ~ 1000으로 정해줬으므로, 그냥 1부터 1000까지를 담고있는 min heap을 만들었다.

    사실 무한대를 담고있는 heap을 어떻게 만들어야할지 모르겠어서 그냥 이렇게했다,, 대충 되겠지뭐,,,

2. int popSmallest()

    smallestinfiniteset의 최소값을 return한다.

    min heap이므로, root를 pop하고 재정렬해준다 (이전에 했던것과 똑같음)

3. void addBack(int num)

    smallestinfiniteset의 맨 뒤에 num을 추가하고 heap을 재정렬한다.

    이 때 중복을 허용하지 않으므로, num값이 이미 heap에 있으면 아무동작도 하지 않는다.

    나는 min heap을 vector로 구현했기때문에 (make_heap을 사용하기 위해서) find함수를 사용해줬다.

    find함수는 vector속에 주어진 인자가 존재하는지 확인한다. 존재하면 해당 인자의 주소를 반환하고, 없으면 vector.end() 값을 반환한다.

 

class SmallestInfiniteSet {
    vector<int> infiniteset;

public:
    SmallestInfiniteSet() {
        
        for(int i = 1; i <= 1000; i++){
            infiniteset.push_back(i);
        }

        make_heap(infiniteset.begin(), infiniteset.end(), greater<>{});
        
    }
    
    int popSmallest() {
        int small = infiniteset[0];
        pop_heap(infiniteset.begin(), infiniteset.end(),greater<>{});
        infiniteset.pop_back(); 

        return small;
    }
    
    void addBack(int num) {
        if(infiniteset[0] <= num){
            // 중복인지 확인필요
            if((find(infiniteset.begin(), infiniteset.end(), num) == infiniteset.end())){
                // 존재하지 않음 -> push
            }else{
                // 존재함 -> 아무동작 하지 않음
                return;
            }

        }
        infiniteset.push_back(num);
        push_heap(infiniteset.begin(), infiniteset.end(),greater<>{});
    }
};

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

 

---

어제부터 heap관련된 함수를 계속 사용하고 있음에도 여전히 이전 코드를 참고하거나 구글링을 했다...

언제외우지,,ㅋ

 

코드의 런타임을 다른 제출물과 비교해주는데 조금 느린편이었다.

 

뭔가 더 효율적인 코드가 있어보이지만,, 생각하기 귀찮아서 그냥 끝내려고한다

미래의 내가 시간부족으로 쓴맛을 보면 해결방법을 찾아보겠지??