Insert Delete GetRandom O(1)

---

💬 문제

[문제 링크]

RandomizedSet 클래스의 네 가지 기능을 구현

RandomizedSet() : 객체 초기화 (생성자)
bool insert(int val) : 객체에 값이 없으면 넣고 true, 있으면 false
bool remove(int val) : 객체에 값이 있으면 삭제하고 true, 없으면 false
int getRandom() : 랜덤으로 객체 내 값 반환 (무조건 1개 이상일 때 부를 것임)

✍️ 나의 풀이

var RandomizedSet = function() {
    this.RandomizedSet = new Map();
    this.list = new Array();
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if (this.RandomizedSet.has(val))
        return false;
    this.RandomizedSet.set(val, this.list.length);
    this.list.push(val);
    return true;
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if (!this.RandomizedSet.has(val))
        return false;
    const index = this.RandomizedSet.get(val);
    const tmp = this.list[index];
    this.list[index] = this.list[this.list.length - 1];
    this.list[this.list.length - 1] = tmp;
    this.list.pop();
    this.RandomizedSet.set(this.list[index], index);
    this.RandomizedSet.delete(val);
    return true;
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    return this.list[Math.floor(Math.random() * this.list.length)];
};

Map과 Array 두 가지를 만들어서 Map은 (실제 값, Array의 인덱스) 저장
Array는 실제 값을 저장하여 getRandom 함수에서 인덱스 접근으로 값을 뽑을 수 있게 함
이 외에 insert, delete 함수에서는 키 보유 판단으로 빠르게 접근
delete를 할 때는 Array에서 해당 인덱스 값과 가장 마지막 값을 swap하여 pop()
swap으로 인해 인덱스 번호가 바뀌었으므로 Map에 다시 set 해준다.

📌 결과

Accepted
Runtime 65ms (Beats 80.40%)
Memory 101.28MB (Beats 33.92%)

📚 러닝 포인트

사실 처음에는 set을 사용해서 구현을 했었다. 그 코드는 다음과 같다.

var RandomizedSet = function() {
    this.RandomizedSet = new Set();
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if (this.RandomizedSet.has(val))
        return false;
    this.RandomizedSet.add(val);
    return true;
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    return this.RandomizedSet.delete(val);
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    const num = Math.floor(Math.random() * this.RandomizedSet.size);
    const setIter = this.RandomizedSet.values();
    for (let i = 0; i < num; i++) {
        setIter.next();
    }
    return (setIter.next().value);
};

자바스크립트에는 실제로 Set이 구현되어 있고, 그 기능을 사용하면 되었기 때문에 굉장이 편하다고 생각하고 있었는데 랜덤 값을 반환할 때 for문을 사용해야했다. 테스트는 통과했지만 문제에서 제시된 조건이 모든 함수의 시간복잡도가 O(1)일 것 이어서 이 방법은 옳지 않았다.

그리고 처음에는 클래스를 구현하라고 해서 constructor를 만들어야 하나 봤더니 기본 틀이 function을 반환하는 거여서 순간 어떻게 해야하지? 생각했다. 다른거는 value를 return 하면 되겠다는 것을 눈치챘지만 생성자 함수는 new Set()을 return 해야 하나 하다가 var obj = new RandomizedSet()로 사용한다고 하니 this.set과 같이 프로퍼티를 선언해주는게 맞았다. 문제는 클래스라고 했지만 준비된 틀은 객체 생성과 해당 객체 인스턴스에 대한 프로토타입을 생성하는 것이었다. 이 부분은 아직 잘 모르는 영역이어서 나중에 TIL로 작성해야겠다.