[Medium] 380. Insert Delete GetRandom O(1)

RandomizedSet 클래스를 구현하세요:

• RandomizedSet(): RandomizedSet 객체를 초기화합니다.
• bool insert(int val): 아이템 val을 집합에 삽입합니다(존재하지 않는 경우). 아이템이 존재하지 않아 성공적으로 삽입되면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
• bool remove(int val): 아이템 val을 집합에서 제거합니다(존재하는 경우). 아이템이 존재하여 성공적으로 제거되면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
• int getRandom(): 현재 집합에 있는 요소들 중 무작위로 하나를 반환합니다(이 메서드가 호출될 때 적어도 하나의 요소가 존재하는 것이 보장됩니다). 각 요소는 동일한 확률로 반환되어야 합니다.

이 클래스의 모든 함수는 평균적으로 O(1) 시간 복잡도 내에서 동작해야 합니다.

 

예시 1:

입력:

["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]

[[], [1], [2], [2], [], [1], [2], []]

 

출력:

[null, true, false, true, 2, true, false, 2]

 

설명:

RandomizedSet randomizedSet = new RandomizedSet(); randomizedSet.insert(1); // 1을 집합에 삽입합니다. 1이 성공적으로 삽입되었으므로 true를 반환합니다. randomizedSet.remove(2); // 2가 집합에 존재하지 않으므로 false를 반환합니다. randomizedSet.insert(2); // 2를 집합에 삽입합니다. true를 반환합니다. 이제 집합에는 [1,2]가 포함되어 있습니다. randomizedSet.getRandom(); // getRandom()은 1 또는 2 중 하나를 무작위로 반환해야 합니다. randomizedSet.remove(1); // 1을 집합에서 제거합니다. true를 반환합니다. 이제 집합에는 [2]가 남아 있습니다. randomizedSet.insert(2); // 2는 이미 집합에 존재하므로 false를 반환합니다. randomizedSet.getRandom(); // 2만 집합에 있으므로, getRandom()은 항상 2를 반환합니다.

 

제약사항:

• -2^31 <= val <= 2^31 - 1
• insert, remove, getRandom 함수는 최대 200,000번 호출될 수 있습니다.
• getRandom 함수가 호출될 때는 반드시 하나 이상의 요소가 자료구조에 존재해야 합니다.

 

풀이

import random

class RandomizedSet:

    def __init__(self):
        self.tin = dict()

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

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

        self.tin.pop(val)
        return True

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


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