380. Insert Delete GetRandom O(1)

문제

Implement the RandomizedSet class:

RandomizedSet() Initializes the RandomizedSet object.

bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.

bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.

int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

접근

#해시테이블 #리스트 #randomized

모든 함수가 O(1)의 시간복잡도를 가져야 하므로, 탐색할 때에 O(n)이 소요되는 리스트는 쓰지 않고 defaultdict인 table을 선언해 구현하였다.
그리고 getRandom은 시간복잡도가 O(1)인 random.choice()를 이용해 선택했다.

하지만 이대로 제출하니 에러가 발생했다. 왜냐하면 random.choice에 table을 넣으면, 값이 0인 키까지 포함해서 선택하기 때문이다. 이를 해결하기 위해 현재 값이 들어있는 리스트인 arr을 선언해 이 리스트로 random.choice를 실행시켰다.

코드

class RandomizedSet:

    def __init__(self):
        self.table = defaultdict(int)
        self.arr = []

    def insert(self, val: int) -> bool:
        if self.table[val] == 0:
            self.table[val] += 1
            self.arr.append(val)
            return True
        else:
            return False

    def remove(self, val: int) -> bool:
        if self.table[val] == 0:
            return False
        else:
            self.table[val] -= 1
            idx = self.arr.index(val)
            del self.arr[idx]
            
            return True

    def getRandom(self) -> int:
        return random.choice(self.arr)
        


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

효율성

Runtime: 1308 ms, faster than 24.17% of Python3 online submissions for Insert Delete GetRandom O(1).
Memory Usage: 61.4 MB, less than 35.00% of Python3 online submissions for Insert Delete GetRandom O(1).