[리트코드] 380. Insert Delete GetRandom O(1)

문제

https://leetcode.com/problems/insert-delete-getrandom-o1/?envType=study-plan-v2&envId=top-interview-150

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.

---

✔ 문제접근 #1 set자료구조활용[통과] ⭕

Intuition
Set자료구조를 활용하여 구현한다.

Algorithm
내부적으로 해시테이블로 구현되어있는 Set은 in, 추가, 삭제등 모두 O(1)에 해결할 수 있다.

class RandomizedSet:

    def __init__(self):
        self.s = set()

    def insert(self, val: int) -> bool:
        if val in self.s:
            return False
        else:
            self.s.add(val)
            return True

    def remove(self, val: int) -> bool:
        if val in self.s:
            self.s.remove(val)
            return True
        else:
            return False
        
    def getRandom(self) -> int:
        return random.choice(list(self.s))

 

Complexity Analysis

• 시간 복잡도 : O(1)

• 공간복잡도 : O(n)
  
  • Set 자료구조 사용

---

✔ 문제접근 #2 해시테이블(dict)[통과] ⭕

Intuition

dict 자료구조를 활용하여 구현한다.

Algorithm
해시 자료구조의 특성상 in, 삽입, 삭제 모두 O(1)에 수행할 수 있다.

class RandomizedSet:

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

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

    def remove(self, val: int) -> bool:
        if val in self.s:
            del self.s[val]
            return True
        else:
            return False
        
    def getRandom(self) -> int:
        return random.choice(list(self.s.keys()))

 

Complexity Analysis

• 시간 복잡도 : O(1)

• 공간복잡도 : O(1)
  
  • dict 자료구조 사용

---

기타풀이 및 회고

요구사항대로 구현만 하면 되는 문제였다. 프로그래밍 언어에는 다양한 set, hash등 여러 자료구조를 지원하기 때문에 손쉽게 해결 할 수 있었다. 자바에서는 HashMap, HashSet자료구로를 활용해서 쉽게 해결할 수 있다.