[heap][hash] heap과 hash 동시사용으로 시간복잡도 효율 높이

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

 

문제

기본 코드

 

오늘의 문제,

 

SmallestIntInfiniteSet에서 자연수로 이루어진 Set를 구현하고 popSmallest(가장 작은값 pop), addBack(값 추가) function을 구현하기

 

(문제에서는 짤렸지만, 1<=<=1000 이 contraint 이며, testcase에서 definition의 total call 수는 at most 1000이다.)

 

popSmallest : heap 자료구조를 사용하면 효율적일 것 (O(lgN))

addBack : 'num'이 현재 존재하지 않는다면 push

heappush를 사용하는 것이 코드길이 및 시간복잡도상 효율적일 것인데 (O(lgN)), 

'num'의 존재여부를 탐색하는데에는 hash (dictionary or set)이 적절 할 것이다. (O(1))

 

 

 

이런 생각하에 우선 부랴부랴 작성해본 코드

import heapq as hq


class SmallestInfiniteSet:

    def __init__(self):
        self.num_set = {i for i in range(1, 1001)} #O(N)
        heap = [i for i in range(1, 1001)]         #O(N)
        hq.heapify(heap)
        self.heap = heap

    def popSmallest(self) -> int:
        if len(self.heap) == 0:
            return None

        popped = hq.heappop(self.heap)
        if len(self.heap) == 0:
            return popped                           # O(lgN)
        self.num_set.remove(popped)
        return popped

    def addBack(self, num: int) -> None:
        if num not in self.num_set:                # O(1)
            self.num_set.add(num)                  # O(lgN)
            hq.heappush(self.heap, num)

 

그냥 call이 1000번 발생한다고 생각했을때에,

                __init__             : 맨 처음 객체 선언 할때에 한 번 call  총 O(2N) = O(N)이긴 하나, 확정적으로 2N(2000)번 연산 발생

 

popSmallest & addBack : 총 1000번 call -> 1000lg(1000) 의 연산 ~= 10,000번

 

대략 12,000번의 연산

 

 

...

 

 

 

 

 

만족스러운 연산량이라 생각은 하나,

 

다른 문제 해결자에 비해 그렇게 효율적인 runtime과 memory를 가져오지는 못한듯...

 

그래서 문제를 다시 생각해보고 또 타 풀이를 보니, 굳이 직접 숫자를 자료구조에 넣을 필요가 없었다...

 

class 이름은 SamllestInfiniteSet, 즉 애초에 모든 수를 관리 할 수 있어야함

 

가장작은 숫자를 self.root=1로 initilize하고 heap과 set을 선언한다.

root : 가장 작은 값 추적

그러나 이전의 나와는 달리,

heap : 제거되었다가 추가된 숫자들을 관리

set : heap에 있는 숫자들을 그대로 포함. (위의 나처럼 탐색에서의 효율을 위해 선언)

 

import heapq as hq

class SmallestInfiniteSet2:
    def __init__(self):
        self.root = 1
        self.min_heap = []
        self.in_heap = set()

    def popSmallest(self) -> int:
        if self.min_heap:
            smallest = hq.heappop(self.min_heap)
            self.in_heap.remove(smallest)
        else:
            smallest = self.root
            self.root += 1
        return smallest

    def addBack(self, num: int) -> None:
        if num < self.root and num not in self.in_heap:
            hq.heappush(self.min_heap, num)
            self.in_heap.add(num)

 

popSmallest :  min_heap이 채워져있다면, (즉, 제거되었다가 추가된 숫자가 있다면) heappop을 반환

                         min_heap이 없다면, root를 반환하고  root +=1 (이는 제거 될 수 있는 수는 1부터 시작해서 연속된 수 밖에 없기 때문이다. 이게 이 풀이의 keyPoint인듯)

 

addBack : 현재 root보다 작고, 추가된적 없는 숫자라면, heap 및 set에 추가

 

이 두 함수에서 결국 heap의 탐색기능을 쓰므로, 위의 내 코드처럼 O(lg(N))의 시간복잡도를 가지지만, 

실질적으로 heap에 들어가있는 숫자가 현저히 적고, 정말 모든 숫자에 대해서 적용가능하므로 효율적이다.

 

그리고 init시의 연산이 1이므로, 약간의 효율성도 가져 올 수 있음

현저히 효율적이게된 runtime 및 memory

 

 

 추가적으로 외울 코드들