[2024] Day16. 380. Insert Delete GetRandom O(1)

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 16일 (화)
Leetcode daily problem

380. Insert Delete GetRandom O(1)

https://leetcode.com/problems/insert-delete-getrandom-o1/description/

Problem

상수 시간 O(1) 내에 삽입(insert), 삭제(remove), 무작위(random)로 요소를 얻을 수 있는 자료 구조를 구현하는 문제이다.

Solution

Data structure, Design pattern

Insert: 삽입 연산은 배열에 요소를 추가하고, 동시에 해당 요소를 해시 테이블에 저장한다. 해시 테이블의 키는 요소로, 값은 해당 요소의 인덱스로 저장한다.

Delete: 삭제 연산은 배열에서 해당 요소를 찾아서 제거한다.
배열의 마지막 요소를 삭제한 위치로 옮겨와서 빈 공간을 채운 후에,
pop을 통해서 상수 시간내에 요소를 제거한다.
마지막 요소로 옮겨진 요소의 인덱스를 업데이트하고, 해시 테이블에서도 해당 요소를 제거한다.

GetRandom: random 라이브러리로 random 모듈을 사용해서 무작위로 요소를 가져온다.

Code

class RandomizedSet:

    def __init__(self):
        self.nums = []
        self.numToIdx = {}

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

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

Complexicity

시간 복잡도

모든 작업은 상수시간 O(1) 이다.

공간 복잡도

공간복잡도는 리스트와 딕셔너리 크기에 비례한다.
O(n)이다.

---