99클럽 코테 스터디 6일차 TIL + 2413/Smallest Number in Infinite Set

2413. Smallest Number in Infinite Set

Medium

---

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.

 

Example 1:

Input
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
Output
[null, null, 1, 2, 3, null, 1, 4, 5]

Explanation
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2);    // 2 is already in the set, so no change is made.
smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set.
smallestInfiniteSet.addBack(1);    // 1 is added back to the set.
smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and
                                   // is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.

 

 

<코드>

import heapq as hq

class SmallestInfiniteSet:

    def __init__(self):
        # self.current = 1
        self.min_heap = list(range(1,1001))
        self.set = set(self.min_heap) #set 의 필요성 몰랐음
        hq.heapify(self.min_heap)
        

    def popSmallest(self) -> int:
        try:
            pop_data = hq.heappop(self.min_heap)
            # if pop_data in self.set:
            self.set.remove(pop_data)
            return pop_data
            
        except IndexError:
            return None
        except KeyError:
            return None

    def addBack(self, num: int) -> None:
        if num < 1 or num > 1000:
            return None
        else :
            if num in self.set:
               return
            else :
                hq.heappush(self.min_heap, num)
                self.set.add(num)
                return None
        
        
# Your SmallestInfiniteSet object will be instantiated and called as such:
# obj = SmallestInfiniteSet()
# param_1 = obj.popSmallest()
# obj.addBack(num)

1. heap 자체로는 중복된 값 방지 할 수없음

그래서 set()을 사용하거나 별도의 최소값 변수를 선언해주는 것이 바람직함

 

2. 어제와 같이 값을 자주 삽입 삭제 때에는 힙 자료구조로 구현된 우선순위 큐를 이용하는것이 바람직함

 

3. 이중 조건문 하기전에 최초 조건문에 이중조건문의 내용을 더 추가하면 수월해짐

 

4. 

 

 

<모범 사례>

class SmallestInfiniteSet:

    def __init__(self):
        self.heap=[]
        self.min_num=1
        
    def popSmallest(self) -> int:
        if self.heap: #self.heap 에 요소 있으면
            return heapq.heappop(self.heap)
        # self.heap 에 요소가 없으면
        self.min_num+=1
        return self.min_num-1
        
    def addBack(self, num: int) -> None:
        if self.min_num>num and num not in self.heap:
        # self.min_num 보다 값이 작다는것은 곧, 이미 한번 pop 된 값 의미
        # num not in self.heap 중복방지
            heapq.heappush(self.heap,num)

1. set() 이용안함 -> 메모리 낭비 줄이기 가능

 

2. 1~1000 까지 값 세팅 안함

그러다 보니 채워진 리스트를 힙속성을 가지게끔 할 필요가 없음

 

3. 중복 여부는 이미 pop 되어서 또 들어갈 수있는 값이거나, 이미 self.heap에 있는지 확인하는 방식임

 

4. min_num에 +1 을 합한후 대입하고, 그 값에다가 -1 을 해서 return 하는 방식도 새로움

 

 

<배운점>

0. 처음으로 리트코드 이용해봤음, 영어라 내심 거리감이 있었는데 막상 해보니 별게 아님

 

1. 중복여부를 가리는 방식으로 set()을 병행에서 이용하면 쉽게 가능함

하지만 꼭 set이 아니더라도 가능함!

 

힙의 최솟값 추적 방식으로 힙을 사용하지 않고, 문제 해결하는 방법임

 

2.