[1스4코2파] # 224 LeetCode 380. Insert Delete GetRandom O(1)

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (224차)
[4코1파] 2023.01.13~ (216일차)
[1스4코1파] 2023.04.12~ (127일차)
[1스4코2파] 2023.05.03 ~ (105일차)

Today :

2023.08.16 [224일차]
380. Insert Delete GetRandom O(1)

380. Insert Delete GetRandom O(1)

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

문제 설명

RandomizedSet Class를 구현하는 문제, 해당 클래스에는 insert, remove, getRandom 메소드가 있다. insert 메소드에는 인자로 int형 val이 들어가는데 해당 val이 있으면 False를 return 없으면 val을 넣고 True로 return 한다.
remove 메소드는 인자로 int형 val을 받고, 해당 val이 있으면 해당 val을 제거하고 True retrun 값이 없으면 false를 return한다.
마지막 getRandom 메소드는 입력됐던 자료들에서 랜덤한 값을 한 개를 return 해주면 된다.
각 메소드의 기능은 시간 복잡도로 O(1)로 수행해야함..

문제 풀이 방법

처음에는 brute force로 풀었다가 O(n), O(1)로 수행하기 위해서는 hash map으로 search 해서 탐색이나 추가, 제거에 O(1)이 되는 자료 구조를 이용해야 했다. 예를들면 set, dictionary
search만 있다면 set을 사용해도 되지만 remove 할 경우를 위해 dictionary와 list를 가지고 insert, remove, getRandom 메소드를 구현한다.
getRandom은 그냥 random 의 choice를 사용하고, insert에서도 search가 필요했는데 이때 O(1) 시간복잡도를 위해 찾은 것은 hash (dictionary)를 사용했다.
제거하는 경우에는 변수 2개를 따로 할당해서 지워야할 val 값과 리스트에 마지막으로 담긴 값을 담아서 pop하고 값을 바꿔주는 걸로 풀이 완

내 코드

 import random

class RandomizedSet:

    def __init__(self):
        self.numList= []
        self.numDict = {}

    def insert(self, val: int) -> bool:
        if val in self.numDict:
            return False
        else:
            self.numDict[val] = len(self.numList)
            self.numList.append(val)
            return True  

    def remove(self, val: int) -> bool:
        if self.numList and val in self.numDict:
            tmp1, tmp2 = val, self.numList[-1]
            self.numList[-1],self.numList[self.numDict[val]] = self.numList[self.numDict[val]], self.numList[-1]
            self.numList.pop()
            self.numDict[tmp2] = self.numDict[tmp1]
            del self.numDict[val]

            return True 
            
        else:
            return False



    def getRandom(self) -> int:
        return random.choice(self.numList)       

증빙

여담

아하!