[Leetcode] 380. Insert Delete GetRandom O(1) - JS

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

 

1. 문제 분석

문제분석
--------------------
insert()
아이템이 존재하지 않으면, 아이템을 set에 삽입한다.
아이템이 존재하지 않으면 true를 반환하고 그렇지 않으면 false를 반환하라.


remove()
아이템이 존재하면, 아이템을 set에서 제거한다.
아이템이 존재했다면 true를 반환하고 그렇지 않으면 false를 반환하라.


getRandom()
현재 set의 요소 중에서 무작위 요소를 반환하라.
최소한 1개의 요소가 존재한다는 것을 보장한다.
무작위 요소가 반환될 확률은 동일해야한다.

제한조건
--------------------
- 클래스의 모든 함수는 시간복잡도가 O(1)이어야 한다.
- -2^31 <= val <= 2^31 - 1
- 2 * 10^5 횟수만큼 insert, remove, getRandom을 호출할 것이다.
- getRandom이 호출될 때 데이터 구조에는 최소한 하나의 요소가 있습니다.

 

2. 접근 방법

접근방법
--------------------
자료구조로 객체를 선택하여 삽입, 제거 시간 복잡도를 O(1)을 할 수 있다.
getRandom()은 객체의 key 배열 중에서 랜덤한 index 값으로 하나를 가져오는 방법으로 구현한다.

 

 

3. 코드

var RandomizedSet = function() {
};

RandomizedSet.prototype.insert = function(val) {
    if (this[val]) {
        return false;
    } else {
        this[val] = true;
        return true;
    }
};

RandomizedSet.prototype.remove = function(val) {
    if (this[val]) {
        delete this[val];
        return true;
    } else {
        return false
    }
};

RandomizedSet.prototype.getRandom = function() {
    const keys = Object.keys(this);
    const randomNums = Math.floor(Math.random() * keys.length);
    return keys[randomNums];
};

 

 

4. 복잡도 분석

- 시간복잡도: O(1)

- 공간복잡도: O(n)