[Leetcode/파이썬] Insert Delete GetRandom O(1)

Insert Delete GetRandom O(1)

---

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.

 

class RandomizedSet:

    def __init__(self):
        self.lst = []
        self.idx_map = {}
        
    def insert(self, val: int) -> bool:
        if val in self.idx_map :
            return False
        self.lst.append(val)
        self.idx_map[val] = len(self.lst) - 1
        return True
        
    def remove(self, val: int) -> bool:
        if val not in self.idx_map :
            return False

        idx = self.idx_map[val]
        self.lst[idx] = self.lst[-1]
        self.idx_map[self.lst[-1]] = idx
        self.lst.pop()
        del self.idx_map[val]
        return True
    
    def getRandom(self) -> int:
        return random.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()

예전에 풀었던 문제던데 언제 풀었지? 언제나 늘 새로운 알고리즘 문제들이다.

문제 조건에 보면 클래스 구현 문제이며, 이 클래스를 시간 복잡도 O(1)로 동작하도록 구현하라는 조건이 있다. 아 그러면 "해시"를 써야겠구나 라고 생각했다. (결국 다른 분의 코드를 참고하였다.) (과거의 내가 이미 다른 분의 코드를 참고하지 않았을까?)

• 초기 상태는 리스트와 딕셔너리를 하나씩 생성한다. 리스트에는 val 값을, 딕셔너리에는 val 값이 어느 인덱스에 저장되어 있는지 표시한다. 
• insert 는 삽입을 위해 val이 현재 lst에 있는지 확인한다. 이때 리스트에 직접 확인을 하게 되면 O(N)의 시간 복잡도를 가지기 때문에 딕셔너리에 삽입되어있는 val : idx 관계를 활용하여 직접 있는지 확인한다. 해시 검색은 O(1) 이다. 동일하게 실제 set() 집합 자료구조나 dict() 딕셔너리 자료구조에서 검색 (안에 들어있나 안 들어있나 확인) 은 O(1) 이다. 
• remove 는 삭제를 위해 val이 현재 lst에 없는지 확인한다. idx_map을 확인하여 val 이 없으면 False. 이후 lst 에 있는 val 을 가장 마지막 인덱스로 바꾼 후 idx_map에도 똑같이 갱신. pop과 del 을 활용하여 리스트와 딕셔너리에 있는 val 을 제거함.
• getRandom은 random 라이브러리를 활용하여 return 하면 된다.

처음에 그냥 set을 사용하면 되지만 문제가 원하는것은 아니라고 생각하여 다음과 같이 접근하려고 했으나 remove에서 많이 헤매다 다른 분의 코드를 참고하여 풀 수 있게 되었다.