Leet Code - Insert Delete GetRandom O(1)

✔️ 문제 링크

https://leetcode.com/explore/learn/card/hash-table/187/conclusion-hash-table/1141/

insert(val), remove(val), getRandom(val)함수를 구현할 때 모두 O(1)의 시간복잡도를 갖게 하는 문제였다.

insert는 그냥 넣는다고 치고.. getRandom도 random()함수를 통해 얻는다고 생각하면 할 수 있겠다 싶엇다.

근데 remove할 때 중간의 값을 빼게되면 하나씩 앞으로 당겨줘야해서 이걸 어떻게 하면 좋을까 고민했는데 삭제하기 전 배열의 마지막값과 삭제하려는 값의 위치를 바꾼다음 pop() 해주면 됐다!

---

코드

var RandomizedSet = function() {
    this.map = {};
    this.nums = [];
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if(this.map[val] === undefined){
        this.nums.push(val);
        this.map[val] = this.nums.length - 1;
        return true;
    }
    return false; //already contain val;
    
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if(this.map[val] === undefined) return false;
    
    const index = this.map[val];
    //swap index and last element
    const length = this.nums.length;
    [this.nums[index], this.nums[length-1]] = [this.nums[length-1], this.nums[index]];
    this.map[this.nums[index]] = index; // nums 배열의 위치 바꿨으니 map의 value값인 index도 바꿔주는 것임
    //remove lastone
    this.nums.pop();
    delete this.map[val];
    return true;
};

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