Insert Delete GetRandom O(1) 풀이

문제

set 자료구조를 구현하여 Insert, Delete, GetRandom 연산을 O(1)으로 수행할 수 있게 하라는 문제

 

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 풀이

기본적으로 set 자료형에는 add라는 insert 함수와 remove, discard라는 delete 내장 함수가 존재함.

add는 O(1), remove/discard도 O(1).. 파이썬에서 set는 해쉬 테이블로 구현되어 있기 떄문에 삽입연산이나 삭제연산이나 모두 평균 시간복잡도가 O(1)

문제는 GetRandom 함수임. 원래 set에서는 pop이라는 O(1)짜리 랜덤 삭제 내장함수가 있지만 여기서는 원소가 삭제되면 안되고, return된 결과값에서 등장한 비율이 일정해야한다는 제한 조건이 있어 인덱싱으로 접근.. 

의문인 점은 처음에는

def getRandom(self) -> int:
    return list(self.RS)[0]

 

하니까 틀림.. 알아보니 set를 list로 변환할 때 랜덤한 순서로 배치되는게 아니고, set 자료구조 내 해쉬테이블에 따라 배치된다고 한다.

 

코드

class RandomizedSet:

    def __init__(self):
        self.RS = set([])

    def insert(self, val: int) -> bool:
        leng = len(self.RS)
        self.RS.add(val)
        return True if len(self.RS) != leng else False

    def remove(self, val: int) -> bool:
        leng = len(self.RS)
        try:
            self.RS.remove(val)
            return True
        except: return False

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