LeetCode 풀기 - 380. Insert Delete GetRandom O(1)

380. Insert Delete GetRandom O(1)

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

Insert Delete GetRandom O(1) - LeetCode

문제)

솔루션1)

• hash 자료구조 사용
• getRandom()은 random.choice() 사용

class RandomizedSet:

    def __init__(self):
        '''
        Initializes the RandomizedSet object.
        '''
        self.d = {}
        

    def insert(self, val: int) -> bool:
        '''
         Inserts an item val into the set if not present. 
         Returns true if the item was not present, false otherwise.
        '''
        if val in self.d:
            return False                
        self.d[val] = None
        return True            

    def remove(self, val: int) -> bool:
        '''
        Removes an item val from the set if present. 
        Returns true if the item was present, false otherwise.
        '''
        if val not in self.d:
            return False        
        del self.d[val]
        return True
        

    def getRandom(self) -> int:
        '''
        Returns a random element from the current set of elements 
        (it's guaranteed that at least one element exists when this method is called). 
        Each element must have the same probability of being returned.
        '''
        return random.choice(list(self.d.keys()))

솔루션2)

• hash, arr 두 자료구조 사용하고 random 모듈을 사용하지 않도록 구현
• hash 자료구조
  • key=val
  • value=val 값이 arr 자료구조에 추가된 idx
• arr 자료구조 : val을 추가
• getRandom() 함수는 random 모듈을 사용하지 않고 arr에 바로 접근해서 O(1) 만족

import time
class RandomizedSet:

    def __init__(self):
        '''
        Initializes the RandomizedSet object.
        '''
        # key=val, val=idx
        self.d = {}
        # val
        self.arr = []
        

    def insert(self, val: int) -> bool:
        '''
         Inserts an item val into the set if not present. 
         Returns true if the item was not present, false otherwise.
        '''
        if val in self.d:
            return False                
        self.d[val] = len(self.arr)
        self.arr.append(val)
        return True            

    def remove(self, val: int) -> bool:
        '''
        Removes an item val from the set if present. 
        Returns true if the item was present, false otherwise.
        '''
        if val not in self.d:
            return False        
        
        # 이동
        val_idx = self.d[val]
        self.arr[val_idx] = self.arr[-1]        
        self.d[self.arr[val_idx]] = val_idx
        
        # 삭제
        self.arr.pop()
        del self.d[val]
        
        return True
        

    def getRandom(self) -> int:
        '''
        Returns a random element from the current set of elements 
        (it's guaranteed that at least one element exists when this method is called). 
        Each element must have the same probability of being returned.
        '''
        random_idx = time.time_ns() %  len(self.arr)
        return self.arr[random_idx]
        
        


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()