99클럽 코테 스터디 3일차 TIL + Heap - Smallest Number in Infinite Set

'

🔗 2336. Smallest Number in Infinite Set

이 문제 또한 heap 을 사용하면 훨씬 실행속도가 빨랐다. 

<문제 요약>

• 1~1000 의 숫자가 있는 set 에서 popSmallest 를 하면 가장 작은 숫자를 반환하고
• addBack 을 하면 숫자를 추가한다. 당연히 집합이므로 같은 숫자는 들어갈 수 없어야 한다.

<실행속도 빠르게 하기>

• min( ) 으로 최소값을 찾았을 때 실행속도가 상당히 느렸다.

• heapq를 사용하면 속도가 빨라졌으나 나보다 빠른 사람들이 훨씬 많았다

• heapq를 사용하면서 Counter를 사용한 예시를 봐서 따라해 봤는데 더 빨라졌다. 

• Counter 란? 🙄 - 출처: 파이썬 공식문서                   
  • Counter 란 hashable 한 object를 count 하는 dict의 subclass 이다. 이 문제에서 사용한다면 set 안에 num 이 있는 지 없는 지 확인할 때 쓸 수 있다. hash를 사용함으로 속도가 빨라진다.

<느낀점>

• 실행속도 비교가 가능해서 어떻게 하면 더 빠르게 만들 수 있는 지 비교해 보는 시간이 재밌었다.

import heapq
from collections import Counter


class SmallestInfiniteSet:
    def __init__(self):
        self.heap = list(range(1, 1001))
        heapq.heapify(self.heap)
        self.dictionary = Counter(self.heap)
        
    def popSmallest(self):
        val = heapq.heappop(self.heap)
        self.dictionary[val] = 0
        return val

    def addBack(self, num: int):
        if num not in self.dictionary or not self.dictionary[num]:
            heapq.heappush(self.heap, num)
            self.dictionary[num] = 1