[스파르타] 99클럽 2기 코테스터디 6일차 TIL / leet 2336

LeetCode: 2336. Smallest Number in Infinite Set (링크)

 

 

2336. Smallest Number in Infinite Set

 

 

Leet code에서는 문제를 처음 풀어봐서 어떻게 풀어야 할지 헤매다가 블로그를 참고하여 풀어봤다.

input 형태가 백준이나 프로그래머스와 다르게 되어 있었는데 이해하고 나니 생각보다 간단했다.

 

문제를 요약하면 다음과 같다. 무한한 양의 정수가 있는 집합 하나가 있고, __init__에서 생성한 빈 집합 black이 있다. 여기에서 우리는 popSmallest를 했을 때 무한한 양의 정수 집합에서 최솟값을 리턴하고 그 값을 무한양수집합에서 제거해야 한다. 그러므로 제일 처음에 popSmallest를 하게 되면 가장 작은 값인 1이 리턴된다. 다음에 또다시 popSmallest를 하게 되면 1을 제외하고 가장 최솟값을 찾아야 하는데, 이 과정을 위해 집합 black을 사용하게 된다. 최솟값을 리턴할 때마다 집합 black에 그 값이 있는지 확인하고 없으면 리턴, 있다면 +1 한 값을 다시 집합 black에서 찾아서 유무를 판단 후 리턴해야 한다. 

 

__init__: 클래스의 새 인스턴스가 생성되면 자동으로 호출된다. 빈 집합을 설정해줘야 함.

popSmallest(): 현재 집합에서 가장 작은 숫자를 제거하고 반환해야 함

addBack(num): 집합에 숫자를 다시 추가한다. 현재 집합에 num이 없는 경우에만 추가할 수 있음.

 

아래 참고한 블로그에서 예시를 줬는데 다음과 같다. 읽고 나면 문제가 이해된다.

SmallestInfiniteSet은 다음의 일련의 과정을 수행한다.

 

1. popSmallest() 4번 반복 호출

2. addBack(2) 호출

3. pop Smallest() 2번 더 호출

 

[출력 결과]

(1) SmallestInfiniteSet 클래스를 인스턴스화 하고 집합 black은 빈 값으로 초기화된다.

(2) popSmallest(): 1 리턴, black: {1}

(3) popSmallest(): 2 리턴, black: {1, 2}

(4) popSmallest(): 3 리턴, black: {1, 2, 3}

(5) popSmallest(): 4 리턴, black: {1, 2, 3, 4}

(6) addBack(2): null 리턴, black: {1, 3, 4}

(7) popSmallest(): 2 리턴, black: {1, 2, 3, 4}

(8) popSmallest(): 5 리턴, black: {1, 2, 3, 4, 5}

 

class SmallestInfiniteSet:

    def __init__(self):
        self.black = set()

    def popSmallest(self) -> int:
        i = 1
        while i in self.black:
            i += 1
        self.black.add(i)
        return i

    def addBack(self, num: int) -> None:
        self.black.discard(num)


# Your SmallestInfiniteSet object will be instantiated and called as such:
# obj = SmallestInfiniteSet()
# param_1 = obj.popSmallest()
# obj.addBack(num)

오늘 미들러 풀이 끝!

---

참고한 블로그: https://algo.monster/liteproblems/2336

2336. Smallest Number in Infinite Set - In-Depth Explanation