[LeetCode] 2349. Design a Number Container System (Python)

Problem

 

Solution

hash

 

change : 해당 index에 number를 저장하거나 이미 index에 Number 가 저장되어있으면 업데이트

find: number에 대해서 어떤 인덱스에 존재하는지를 찾는다. number가 저장된 index 가 많으면 가장 최솟값 반환, 없으면 -1 반환

 

dict를 사용해야겠다고 생각했고 value 는 list로 구현해서 sorted 로 최솟값을 구해야겠다고 생각했다.

그런데 SortedSet이 있는지 몰랐는데 이걸 사용하니 따로 sorted 를 안해주어도된다!

 

그리고 어떤 index 에 number 가 저장되어있는지 기록하는 변수 d,

각 number 에 어떤 indicies들이 저장되어있는지 기록하는 변수 map 을 사용했다.

 

Change

change 에서 map[number]에 index 저장, d[index]=number 로 저장. 만약 d에 index가 존재하면

기존에 존재하던 prevNum = d[index] 를 찾아서 map[prevNum]에서 index를 제거하고, map[numer] (새로운 number)에 index 저장. 그리고  d[index]=number 업데이트해준다.

 

Find

map[number]에서 sortedSet 으로 저장되어있으니 가장 첫번째 원소 반환.

만약 없으면 -1 return

 

Code

class NumberContainers:

    def __init__(self):
        self.map = defaultdict(SortedSet)
        self.d = dict()
  
    def change(self, index: int, number: int) -> None:
        #이미 index에 숫자가 존재하면, map에서 index 제거하고 현재 number에 index add
        if index in self.d:
            prevNum = self.d[index]
            self.map[prevNum].remove(index)
        self.map[number].add(index)
        self.d[index] = number


    def find(self, number: int) -> int:
        li = self.map[number]
        if len(li) > 0:
            return li[0]
        return -1



# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)

 

Complexity

Time Complexity

• change
  • map[prevNum].remove(index) => O(logN)
  • d[index] = number => O(1)
  • 총 O(logN)
• find
  • li = map[number] => O(1)
  • return li[0] => O(1)
  • 총 O(1)

Space Complexity

d => n개의 인덱스 저장 => O(N)

map => number 마다 SortedSet 유지, 전체적으로 N개의 인덱스 저장 => O(N)