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

https://leetcode.com/problems/insert-delete-getrandom-o1/description/?envType=daily-question&envId=2024-01-16

LeetCode - The World's Leading Online Programming Learning Platform

시간복잡도 O(1)만에 삽입, 삭제, random으로 return 하는것을 구현하는 문제이다.

---

문제에서는 스켈레톤 코드로 크게 4가지 메서드를 주었고, 채워야한다.

class RandomizedSet:

    def __init__(self):
        

    def insert(self, val: int) -> bool:
        

    def remove(self, val: int) -> bool:
        

    def getRandom(self) -> int:
        


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

 

1. __init__

해당 문제에서는 값을 집어넣을 list도 필요하고, index를 가리키는 hash가 필요해 보인다.

또 문제조건이 O(1)이라서 hash를 강제로 써야만 한다.

    def __init__(self):
        self.List = []
        self.idx_map = {}

 

2. insert

hash에 삽입하려는 value가 있다면 False를 반환

없다면 append

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

 

3. remove

맨 마지막에 들어간 value와 그 value에 해당하는 hash를 불러온다.

그 후 list에서 지울 index를 찾아 pop하고, hash에서는 del 후 True를 반환

만약에 원소가 없다면 False를 반환

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

 

4. getRandom

List에서 random 라이브러리 중 choice를 사용해서 return 한다.

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

 

 

정답

class RandomizedSet:

    def __init__(self):
        self.List = []
        self.idx_map = {}

    def insert(self, val: int) -> bool:
        if val in self.idx_map:
            return False
        self.idx_map[val] = len(self.List)
        self.List.append(val)
        return True
        
    def remove(self, val: int) -> bool:
        if val in self.idx_map:
            last_element, idx = self.List[-1], self.idx_map[val]
            self.List[idx], self.idx_map[last_element] = last_element, idx
            self.List.pop()
            del self.idx_map[val]
            return True
        return False

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


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