Leetcode - 380. Insert Delete Getrandom O(1)

문제 링크

Leetcode - 380. Insert Delete Getrandom O(1)

개요

RandomizedSet 클래스가 주어진다. insert, remove, getRandom을 차례대로 구현해야 한다.

각 메서드의 상세 요구사항은 아래와 같다.

메서드명	요구사항
insert	RandomizedSet에 값을 집어 넣는다. 이 때, 이미 저장되어 있는 값이면 false를 반환하고 값이 성공적으로 저장되면 true를 반환한다.
remove	RandomizedSet에 있는 값을 제거한다. 이 때, 존재하지 않는 값이면 false를 반환하고 값이 성공적으로 삭제되면 true를 반환한다.
getRandom	RandomizedSet에 있는 임의의 값을 반환한다.

insert, remove, getRandom을 최대한 O(1)로 맞춰 구현해야한다. 사실, 문제는 O(n)이 나와도 테스트가 제대로 통과되지만, 최대한 문제의 요구사항을 반영해보자.

모호한 부분

O(1)이 나오려면 hash-table을 이용해야하는건 알겠다.

그러나 값이 있는지, 없는지 확인하기 위해선 hash-table에 있는 전체 item을 검사해야하는게 아닌가? 싶어서 평균 O(n)이 나오지 않을까 생각했다.

그러나 이 생각은 틀렸다. hash_table은 직접 key 값을 이용해 접근하므로, key값의 계산이 맞지 않으면 바로 false를 뱉어낼거라 분석된다.ㄴ

파이썬에서 사용하는 Collection 관련 알고리즘의 시간 복잡도를 조사해보니, val in hash-table연산을 하였을 때, 평균 O(1)이 나오고 Worst-Case는 O(n)이 나온다고 한다.

각 프로그래밍 언어별 시간 복잡도 정보

• TimeComplexity - Python wiki
• Collecrtion TimeComplexity - java

Set으로 충분히 해결할 수 있을거라 생각했으나, Set은 unorderd-list이므로 List와 다르게 item 인덱스를 지정하여 꺼낼 수 없다.

따라서 Set으로 꺼내기 위해서는 List로 변환하여 item 개수 미만인 Random한 index로 조회해야 한다.

해결 전략

해결 방법은 Set을 사용하지 않고, List와 HashTable을 사용하며 해결할 수 있다.

각 메서드 별 해결 전략을 알아보자.

insert

List를 이용하여 값을 저장한다. 값의 존재여부를 파악하기 위해 HashTable에 저장된 값의 List index를 관리한다.

List에 값을 저장할 때 O(1)이고, 값의 존재여부를 파악할 때, HashTable을 사용하게 되므로 O(1)이다.

class RandomizedSet:
    def __init__(self):
        self._item_list = []
        self._item_index_table = dict()

    def insert(self,val : int) -> bool:
        if val in self._item_index_table:
            return False

        self._item_list.append(val)
        self._item_index_table = len(_item_list) - 1
        return True

remove

HashTable을 이용해 값이 존재하는지 확인한다. 값이 존재하지 않으면 False를 반환하고, 값이 존재하면 제거 준비를 한다.

제거는 아래와 같은 순서로 이루어진다.

1. 제거할 값의 index를 저장한다.
2. 마지막에 저장한 값을 임시로 저장한다.

3. 제거할 값의 index에 마지막에 저장한 값을 덮어씌운다.
4. HashTable에 마지막에 저장한 값의 index를 제거할 값의 index로 덮어씌운다.

5. List의 맨 마지막 값을 제거한다 : O(1)
6. HashTable에 제거할 값 정보를 제거한다. : O(1)

비록 item의 순서는 보장되지 않지만, 이러한 일련의 과정을 거치게되면 O(1)을 보장된 삭제를 할 수 있게 된다.

class RandomizedSet:
    def remove(self,val : int) -> bool:
        if val not in self._item_index_table:
            return False

        removed_index = self._item_index_table(val)
        latest_val = self._item_list[-1]

        self._item_list[removed_index] = latest_val
        self._item_index_table[latest_val] = removed_index

        self._item_list.pop()
        del self._item_index_table[val]

        return True

getRandom

list의 size계산이 O(1)이므로 random.choice를 이용하여 구현이 가능하다.

import random
class RandomizedSet:
    def getRandom(self) -> int:
        return random.choice(self.item_list)

회고

중복되지 않은 값의 저장 및 조회 그리고 저장된 값을 추출하는 것을 O(1)로 하는 방법들을 익히게 된 시간이 된 것 같다.

특히, 값을 제거할 때 제거할 값의 index에 마지막에 들어간 값을 대체하는 방식은 꽤나 인상적이였다.

같은 상황이 생길 경우, 이를 이용해서 해결해봐야겠다.

#coding-interview

Comments