[Leetcode/Python] 380. Insert Delete GetRandom O(1)

문제 링크

Insert Delete GetRandom O(1) - LeetCode

 

문제 설명

RandomizedSet 클래스를 구현합니다.

- RandomizedSet() RandomizedSet 개체를 초기화합니다.
- bool insert(int val) 항목 val이 없으면 집합에 삽입합니다. 항목이 없으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
- bool remove(int val) 항목 val이 있는 경우 세트에서 항목 val을 제거합니다. 항목이 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
- int getRandom() 현재 요소 집합에서 임의의 요소를 반환합니다(이 메서드가 호출될 때 적어도 하나의 요소가 존재함을 보장합니다). 각 요소는 반환될 확률이 같아야 합니다.

각 함수가 평균 O(1) 시간 복잡도로 작동하도록 클래스의 함수를 구현해야 합니다.

 

입출력 예시

입력
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]

출력
[null, true, false, true, 2, true, false, 2]

제한 사항

 

• -2^31 <= val <= 2^31 - 1
• 최대 2 * 10^5 개의 호출이 생길것 이다.
• getRandom이 호출될 때 데이터 구조에 하나 이상의 요소가 있다.

 

 

문제 풀이

 간단히 stack을 쓰면 될것같지만, 이 경우 시간복잡도가 O(n)이 된다. 문제에서 요구하는 O(1)의 시간복잡도를 얻으려면 해시 함수를 써야한다.

 

 이 문제는 해시 함수를 쓰는 것과 클래스를 다루는 것을 둘 다 할 수 있어야 한다. 문제 자체는 쉽지만, 다른사람의 코드를 참고해서 어떻게 클래스를 효율적으로 쓰는지 공부해보자.

 

소스코드

class RandomizedSet:

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

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

    def remove(self, val: int) -> bool:
        if val in self.dict.keys():
            del self.dict[val]
            return True
        else:
            return False

    def getRandom(self) -> int:
        keys = list(self.dict.keys())
        return random.choice(keys)

 

 

코딩 테스트, 어떻게 대비해야 할까?