[LEETCODE 150] - 380 Insert Delete GetRandom O(1)

LeetCode의 380번인 " Insert Delete GetRandom O(1)" 문제를 풀어봤다

 

이문제에서는 스켈레톤 코드로 크게 4가지의 메서드를 주었고, 그거에 대해 채워야한다.

 

문제해결은 시간복잡도 O(1)만 삽입,삭제,random으로 return하는 것을 구현하는 문제이다.

 

---

1. “리스트 + 해시맵을 같이 써서” 3개 연산을 평균 O(1)로 만들기

__init__ : 초기화

import random

class RandomizedSet:
	def __init__(self):
    	self.numMap = {} # 정수를 인덱스와 매핑하는 딕셔너리
        self.numList = [] # 정수 값을 저장하는 리스트

• numMap은 특정 정수를 리스트 내의 인덱스와 매핑하여 저장하는 딕셔너리 이다. 이를 통해 값의 빠른 검색이 가능해진다.
• numList는 집합의 정수 값을 저장하는 리스트이다.

insert : 삽입

def insert(self, val: int) -> bool:
	res = val not in self.numMap # val이 이미 존재하는지 확인
    if res:
    	self.numMap[val] = len(self.numList) # 새로운 값을 리스트의 마지막 인덱스에 매핑
        self.numList.append(val) #리스트에 val 추가
    return res

• 주어진 val이 numMap에 존재하지 않는 경우(res 가 True인 경우)만 삽입된다.
• val의 인덱스를 numMap에 저장하고, val을 numList에 추가한다.
• 이미 존재하면 False를 반환하고, 그렇치 않으면 True를 반환한다.

remove: 삭제

def remove(self, val: int) -> bool:
	res = val in self.numMap # val이 존재하는지 확인
    if res:
    	idx = self.numMap[val] # val의 인덱스 가져오기
        lastVal = self.numList[-1] #리스트의 마지막 값 가져오기
        self.numList[idx] = lastVal # 현재 인덱스의 값을 마지막 값으로 대체
        self.numList.pop() #마지막 값을 리스트에서 제거
        self.numMap[lastVal] = idx # 마지막 값을 새 인덱스에 매핑
        del self.numMap[val] # val을 numMap에서 삭제
    return res

• val이 numMap에 존재하는 경우만 삭제된다.
• 해당 값의 인덱스를 찾아 numList의 해당 위치에 마지막 요소를 옮긴다. 이는 삭제로 인한 리스트의 비어있는 자리를 매꾼다.
• 삭제된 값을 numMap에서 제거하고, 마지막 요소의 인덱스를 업데이트 한다.
• 성공적으로 제거되면 True, 존재하지 않으면 False를 반환한다.

getRandom : 무작위 요소 반환 

def getRandom(self) -> int:
	return random.choice(self.numList) # 리스트에서 랜덤으로 값 반환

• random.choice함수를 사용하여 numList의 요소 중 하나를 무작위로 반환한다. 이때 numList는 항상 현재 집합의 상태를 반영하므로, 정확한 값을 반환할 수 있다.

전체적인 설계

• 이 자료구조는 중복을 허용하지 않는 정수 집합을 효율적으로 관리할 수 있는 방법을 제공한다.
• insert 와 remove 함수는 O(1)시간 복잡도로 수행되며, getRandom 또한 O(1) 시간 복잡도로 무작위 값을 반환한다.
• 리스트와 딕셔너리를 함께 사용하여 삽입 및 삭제시 컨시스턴시를 유지하며, 빠른조회가 가능하다.