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

📌 LeetCode [380]: Insert Delete GetRandom O(1)

🔗 문제 링크

---

문제 설명 📄

다음의 연산을 평균적으로 O(1) 시간 복잡도로 지원하는 자료 구조를 설계하세요:

1. insert(val) : 값을 삽입합니다. 값이 이미 존재하면 False를 반환하고, 그렇지 않으면 True를 반환합니다.
2. remove(val) : 값을 삭제합니다. 값이 존재하지 않으면 False를 반환하고, 그렇지 않으면 True를 반환합니다.
3. getRandom() : 자료 구조에서 임의의 값을 반환합니다. 각 값은 동일한 확률로 선택됩니다.

---

문제 해결 접근 방법 🔍

• 딕셔너리와 리스트를 조합하여 구현:
  • 딕셔너리는 값의 인덱스를 빠르게 접근하기 위해 사용합니다.
  • 리스트는 getRandom 연산에서 임의의 값을 O(1)로 선택하기 위해 사용합니다.
• 삽입 연산:
  • 값이 딕셔너리에 없다면, 리스트 끝에 값을 추가하고 딕셔너리에 해당 값의 인덱스를 저장합니다.
• 삭제 연산:
  • 삭제할 값을 딕셔너리에서 확인 후, 리스트의 마지막 값을 삭제할 값의 위치로 이동하여 O(1)로 삭제합니다.
• 랜덤 선택 연산:
  • 리스트에서 임의의 인덱스를 선택하여 값을 반환합니다.

---

Solution 💻

import random

class RandomizedSet:

    def __init__(self):
        self.dic = {}
        self.arr = []

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

    def remove(self, val: int) -> bool:
        if val not in self.dic:
            return False
        idx = self.dic[val]
        last_val = self.arr[-1]
        self.arr[idx] = last_val
        self.dic[last_val] = idx
        self.arr.pop()
        del self.dic[val]
        return True

    def getRandom(self) -> int:
        rand_idx = random.randint(0, len(self.arr) - 1)
        return self.arr[rand_idx]

---

시간 복잡도 분석 ⏲️

• 삽입: O(1)
• 삭제: O(1)
• 임의 선택: O(1)
• 총 시간 복잡도: O(1)

---

공간 복잡도 분석 🗄️

• 딕셔너리: O(n), 삽입된 값의 개수에 비례.
• 리스트: O(n), 삽입된 값의 개수에 비례.
• 총 공간 복잡도: O(n)

---