380. Insert Delete GetRandom O(1) (Array, Hash Table, Math, Design, Randomized)

링크 - https://leetcode.com/problems/insert-delete-getrandom-o1/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

우리는 해시테이블과 stack을 사용해서 문제를 풀 수 있다.

1. 값이 들어오면 val이 해시테이블에 있는지 살피고 없으면 현재 stack길이를 인덱스로 해서 해시테이블에 넣어준 뒤 stack에 append한다.

2. 값을 지울때는 val이 해시테이블에 있는지 살피고 있으면 현재 stack의 마지막 원소를 현재 지우려는 stack의 인덱스에 넣어준뒤 stack을 pop하고 해시테이블 키-값을 지워준다.

3. random.choice(list)를 하면 list에 있는 아무 원소를 랜덤하게 반환한다.

Code

class RandomizedSet:

    def __init__(self):
        self.val_to_idx = {}
        self.stack = []

    def insert(self, val: int) -> bool:
        if val in self.val_to_idx:
            return False

        self.val_to_idx[val] = len(self.stack)
        self.stack.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.val_to_idx:
            return False

        last_element = self.stack[-1]
        idx_to_remove = self.val_to_idx[val]
        self.stack[idx_to_remove] = last_element
        self.val_to_idx[last_element] = idx_to_remove
        self.stack.pop()
        del self.val_to_idx[val]
        return True

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


# 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()

Complexity

Time Complexity: O(1)

Space Complexity: O(N)