380. Insert Delete GetRandom O(1)

380. Insert Delete GetRandom O(1)

 

https://youtu.be/j4KwhBziOpg?si=oBpHxLpob44XbDSt

 

 

• O(1) 는 hashset 으로 푸는 것임
• index 번호를 hashset 으로.
• random 뽑기와 average 도 O(1)로 풀어야되므로, List도 사용해야함

 

class RandomizedSet:

    def __init__(self):
        self.numMap = {}  # 값 -> 리스트의 인덱스를 매핑하는 딕셔너리
        self.numList = []  # 실제 값들을 저장하는 리스트

    def insert(self, val: int) -> bool:
        res = val not in self.numMap # 없으면(if the item was not present) True
        if res: # True 면 없는 경우
            # 리스트의 인덱스 값으로 넣어줌
            # 리스트의 인덱스를 numMap에 저장 (값 -> 인덱스 매핑)
            self.numMap[val] = len(self.numList) 
            # 이제 리스트에 값을 넣었으니, 윗줄에서 numMap[val]매핑한 index 값과 같아짐
            # 리스트에 값을 추가 (리스트의 인덱스가 numMap[val]과 동일해짐)
            self.numList.append(val) 
        return res # 값이 새롭게 추가되었는지 여부 반환 (True: 추가됨, False: 이미 존재)


    def remove(self, val: int) -> bool:
        res = val in self.numMap # 있으면(if the item was present,) True
        if res: # 있으면
            # 마지막에 추가된 값(lastVal)을 val 에 매핑된 numMap 으로 넣어주고,
            idx = self.numMap[val]  # 삭제할 값의 인덱스를 가져옴
            lastVal = self.numList[-1]  # 리스트의 마지막 값
            self.numList[idx] = lastVal  # 삭제하려는 값을 마지막 값으로 덮어씀 (공간 재활용)
            # 기존의 lastVal 매핑된 부분들 삭제 
            self.numList.pop() # lastVal 이 리스트의 제일 마지막에 있었음, pop 으로 삭제 
            self.numMap[lastVal] = idx # 마지막 값의 인덱스 정보를 업데이트
            del self.numMap[val]   # 딕셔너리에서 삭제하려는 값의 매핑을 제거
        return res  # 값이 삭제되었는지 여부 반환 (True: 삭제됨, False: 존재하지 않음)


    def getRandom(self) -> int:
    	# 리스트에서 랜덤하게 값 하나를 반환
        # random.choice는 리스트에서 O(1)로 랜덤 값을 선택 가능
        return random.choice(self.numList)
        


# 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()