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

380. Insert Delete GetRandom O(1)

Medium

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.

 

Example 1:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

 

Constraints:

• -231 <= val <= 231 - 1
• At most 2 * 105 calls will be made to insert, remove, and getRandom.
• There will be at least one element in the data structure when getRandom is called.

---

문제 풀이

• 함수를 완성시키는 문제인데, 함수들이 각각 초기화, 삽입, 삭제, 랜덤 숫자 뽑기가 있다.
• 문제의 제한사항을 보면 모든 함수가 동작시 상수시간에 작동을 해야만한다.
• 삽입과 삭제는 O(1) 시간에 작동하는 딕셔너리를 사용할 수 있다.
• 하지만 랜덤 숫자 선택에서는 파이썬의 choice 함수를 사용할 수 있는데, 이 함수는 딕셔너리를 사용할 수 없다.
• 그래서 딕셔너리와 대응할 리스트를 만든다.
• 딕셔너리의 키는 숫자가 되고 값은 인덱스가 된다. 
• 여기서 인덱스는 생성된 리스트에 어느 위치에 숫자가 있는지를 의미한다.
• 삽입을 할때 숫자가 있는지 확인하기 위해서 딕셔너리를 사용하면 O(1) 상수시간안에 함수가 종료될 것이다. 
• 그리고 딕셔너리에 존재하지 않는다면 키에 숫자를 넣고 값 부분에 새로 만든 리스트의 현재 최대길이(인덱스)를 넣는다.
• 마지막으로 그 숫자를 리스트에도 넣는다. 
• 삭제를 할때는 현재 리스트의 마지막 숫자를 저장하고, 현재 지울 숫자의 인덱스를 딕셔너리에서 가져온다.
• 현재 지울 숫자의 인덱스를 사용하여 리스트에 마지막에 있던 값을 현재 지울 숫자의 위치에 덮어 쓴다.
• 그리고 딕셔너리에서 덮어쓴 숫자의 인덱스 값을 현재 지울 숫자의 인덱스로 덮어 쓴다.
• 마지막으로 리스트의 마지막 숫자를 빼고 딕셔너리에서 지울 숫자를 제거한다. 
• 그리고 랜덤 숫자를 뽑을때는 리스트를 가지고 choice 함수를 사용한다. 
• 랜덤으로 숫자를 상수 시간에 뽑기위해서 choice 함수를 사용하지만 이 함수는 리스트에서 사용할 수 있다.
• 그렇기 때문에 insert 와 remove 의 시간복잡도가 O(1) 인 딕셔너리를 사용한 것이다.
• 그리고 그 딕셔너리와 대응하여 리스트를 사용했으며, 숫자를 지울때는 항상 숫자를 리스트에서 제거하기 전에 리스트의 마지막 숫자를 지울 숫자가 있는 리스트 위치에 덮어 쓴다. 
• 이렇게 딕셔너리와 리스트를 연결하여 유지할 수 있다.

소스 코드

class RandomizedSet:

    def __init__(self):
        self.d = {}
        self.lst = []

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

    def remove(self, val: int) -> bool:
        if val in self.d:
            last, idx = self.lst[-1], self.d[val]
            self.lst[idx], self.d[last] = last, idx
            self.lst.pop()
            del self.d[val]
            return True
        return False

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


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