LeetCode - Insert Delete GetRandom O(1)

wodnr_P·2023년 10월 8일

Insert Delete GetRandom O(1)List leetcode 알고리즘

LeetCode Top Interview 150

목록 보기

29/32

⭐️ LeetCode 알고리즘 풀이 (with Python)

# Insert Delete GetRandom O(1)

[Quetion]

LeetCode 380. Insert Delete GetRandom O(1)

📌 접근법

[문제 이해]

문자열 삽입, 삭제, 랜덤 조회 함수 만들기

평균 O(1)의 시간복잡도

이미 문자열이 있을 때 삽입시 False

문자열이 없을 때 삭제시 False

O(1)의 시간복잡도로 접근하기 위해서는 Hashmap을 활용해야 겠다고 생각했다.

문자열이 없을 때 삭제시 False를 반환하는 것은 stack을 구현할 때의 stack underflow가 떠올랐다.

💻 구현

class RandomizedSet:
    def __init__(self):
        self.ran_set=[]
        self.ran_hash={}
    
    def insert(self, val: int) -> bool:
        if val in self.ran_hash.keys():
            return False
        else:
            self.ran_hash[val]=None
            self.ran_set.append(val)
            return True
    
    def remove(self, val: int) -> bool:
        try:
            del self.ran_hash[val]
            self.ran_set.remove(val)
            return True
        except KeyError:
            return False
    
    def getRandom(self) -> int:
        return random.choice(self.ran_set)

Runtime: 349ms | Memory: 63.5MB
LeetCode 코드 중 Runtime 53%, Memory 95% 해당하는 결과

📌 로직 핵심

ran_hash 딕셔너리에 데이터를 key 값으로 저장
in 연산자로 이미 key가 있는지 확인
try except 구문으로 딕셔너리에 key 값이 없는 경우 처리
random.choice() 라이브러리 및 함수로 동일 확률 랜덤하게 원소 조회

📝 Insert Delete GetRandom O(1) 회고

시간복잡도는 O(1), 공간복잡도는 O(N)이 나왔다.
dictionary.get('key')로 key값이 없으면 None으로 확인가능 했지만 key가 있음에도 None이 출력되는 상황을 발견해서 try except 구문으로 KeyError를 응용하여 구현했다.
리스트와 딕셔너리를 모두 사용하며 삽입, 삭제하기 때문에 조금 비효율적이라고 생각해서 set()의 특징을 활용하여 개선해보았다.

class RandomizedSet:
    def __init__(self):
    	# ran_hash를 중복이 없는 집합으로 선언
        self.ran_hash=set()
    
    def insert(self, val: int) -> bool:
        if val in self.ran_hash:
            return False
        self.ran_hash.add(val)
        return True

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