[LeetCode/Python] Insert Delete GetRandom O(1)

Problem

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.

RandomizedSet 클래스를 구현하는 문제이다.

• RandomizedSet()는 RandomizedSet 객체를 초기화한다.
• bool insert(int val)은 아이템 val이 set에 존재하지 않을 경우 set에 삽입한다.
  아이템이 존재하지 않으면 True를 반환하고 아이템이 존재하면 False를 반환한다
• bool remove(int val)은 아이템 val이 set에 존재할 경우에 set에서 삭제한다. 아이템이 존재하면 True를 반환하고 아이템이 존재하지 않으면 False를 반환한다.
• int getRandom()은 현재 set에 존재하는 요소 중 하나를 랜덤하게 반환한다. (이 메서드가 호출될 때 최소한 하나의 요소가 존재하는 것이 보장된다)
  각 요소가 반환될 확률은 모두 같아야 한다.

클래스의 각 함수가 평균 O(1)의 시간복잡도를 갖도록 구현해야 한다.

Solution

list를 사용해 구현하기

시간복잡도를 생각하지 않고 구현했을 때 가장 간편한 방법은 리스트를 이용하는 것이다.

from random import choice

class RandomizedSet:

    def __init__(self):
        self.data = []

    def insert(self, val: int) -> bool:
        if val not in self.data:
            self.data.append(val)
            return True
        return False

    def remove(self, val: int) -> bool:
        if val in self.data:
            self.data.remove(val)
            return True
        return False
        
    def getRandom(self) -> int:
        if self.data:
            return random.choice(self.data)

• 각 메서드는 요구조건에 부합하지만 시간복잡도는 평균 O(N)이다.
• 리스트는 순차탐색을 하기 때문에 val이 리스트 내부에 존재하는지 확인하는 연산의 시간 복잡도는 O(N)이다. val이 존재하지 않는 경우나 val이 리스트의 맨 끝에 존재하는 경우 처음부터 끝까지 탐색해야 하기 때문이다.
• 파이썬의 list도 내부적으로는 배열로 구현되어 있다. 새로운 요소를 삽입할 때 내부의 capacity가 가득찬 경우에는 새로운 크기의 배열을 할당해야 하므로 평균 시간복잡도는 O(N)이다.
• 삭제 연산의 경우에도 삭제할 요소가 존재하는지 순차 탐색을 진행해야 하므로 평균 시간복잡도는 O(N)이다.

Dictionary를 사용해 구현하기

from random import choice

class RandomizedSet:

    def __init__(self):
        self.data = {}

    def insert(self, val: int) -> bool:
        if val not in self.data:
            self.data[val] = 1
            return True
        return False

    def remove(self, val: int) -> bool:
        if val in self.data:
            self.data.pop(val)
            return True
        return False
        
    def getRandom(self) -> int:
        if self.data:
            return random.choice(list(self.data))

• 파이썬의 딕셔너리는 내부적으로 해쉬테이블을 이용해서 구현되어 있다.
• 해시테이블은 리스트 혹은 배열을 사용해서 key-value 쌍으로 값을 저장하는 자료구조이다. 또한 해시 함수를 사용하여 주어진 키와 관련된 데이터를 저장하거나 검색하기 위한 인덱스를 결정한다.
• 해시테이블은 key에 해시함수를 적용한 값을 인덱스로 사용하기 때문에 상수 시간에 접근이 가능하므로 시간복잡도는 O(1)이다.