[Leetcode]_380. Insert Delete GetRandom O(1)

문제

https://leetcode.com/problems/insert-delete-getrandom-o1/?envType=study-plan-v2&envId=top-interview-150 

LeetCode - The World's Leading Online Programming Learning Platform

풀이

기존 메서드를 활용하거나 for 문을 순회하면 쉽게 풀 수 있을 것 같은데 조건에서 모든 메서드는 O(1)의 시간 복잡도를 만족시켜야 한다고 했다.

insert를 할 때에는 배열메서드 append를 사용하면 O(1)을 만족하지만, 매개변수가 set에 포함되어 있는지 아닌지 체크하는 배열 메서드는 O(n)의 시간복잡도를 가지기 때문에 배열만으로는 구현하기 어려워 보인다.

 

그래서 key 값을 통해서 value 값을 바로 참조하는 dictionary 자료구조를 떠올렸다.

 

import random

class RandomizedSet:
    def __init__(self):
        self.data_map = dict()
        self.data = []
    
    def insert(self,val):
        if val in self.data_map:
            return False
        
        self.data_map[val] = len(self.data)
        self.data.append(val)
        return True

    def remove(self,val):
        if not val in self.data_map:
            return False
        
        lastElem = self.data[-1]
        IndexOfRemoveElem = self.data_map[val]
        
        self.data_map[lastElem] = IndexOfRemoveElem
        self.data[IndexOfRemoveElem] = lastElem
        
        self.data[-1] = val
        self.data.pop()
        self.data_map.pop(val)
        return True
    
    def getRandom(self):
        return random.choice(self.data)

• 배열과 dict 자료구조를 선언한다.
• insert 메서드에서 dict 구조에 key 값은 매개변수 값이고 value 값은 배열 구조에서 index로 설정한다.
  • in 연산자로 dict 의 key 값에 매개변수가 있는지 체크한다.
  • 없다면, dict 의 key를 매개변수로 설정하고 value 값은 배열의 맨 마지막에 추가될 것을 감안하여 길이로 설정한다.
  • 왜냐하면 아직 추가되기 전의 길이가 곧 추가되고 난 후의 index이므로...
• remove 메서드에서 배열의 마지막 요소와 제거할 요소를 서로 바꿔주는 작업을 한다.
  • dict 구조에서 마지막 요소의 value를 제거할 요소의 index로 설정한다.
  • 배열구조에서 제거할 요소의 index에 값을 마지막 요소로 설정한다.
  • 배열구조의 마지막 요소를 매개변수 값으로 수정한다.
  • 배열의 마지막 요소를 제거하는 메서드 pop()을 수행한다.
  • dict 구조의 key값 중 매개변수와 동일한 key 값을 제거한다.
• getRandom 메서드는 random 라이브러리를 사용하여 배열 요소 중 랜덤으로 하나를 반환한다.