380. Insert Delete GetRandom O(1)

늘보·2021년 10월 25일

LeetCode

목록 보기

62/69

💡 풀이

class RandomizedSet {
  constructor() {
    (this.map = new Map()), (this.arr = []);
  }

  insert(val) {
    if (this.map.has(val)) return false;
    this.map.set(val, this.arr.length);
    this.arr.push(val);

    return true;
  }

  remove(val) {
    if (!this.map.has(val)) return false;
    let deletedIndex = this.map.get(val);
    this.arr[deletedIndex] = this.arr[this.arr.length - 1];
    this.map.set(this.arr[deletedIndex], deletedIndex);
    this.map.delete(val);
    this.arr.pop();

    return true;
  }

  getRandom() {
    let randomIndex = Math.floor(Math.random() * this.arr.length);
    return this.arr[randomIndex];
  }
}

📝 결과

📝 정리

개인적으로 prototype보다 class로 구현하는게 더 직관적이라고 생각해서 class를 사용하였다!

문제의 요구사항은 '중복을 허용하지 않는 자료구조 Set을 직접 구현해볼 수 있나요?(시간 복잡도 O(1)으로' 였다. remove() 를 구현하는 부분에서 시간이 많이 걸렸다.. 문제 풀이를 설명하면 다음과 같다.

먼저 map과 arr를 준비한다.

`insert()`

insert 메서드는 간단하다. map.set을 이용해 val값을 key로, this.arr.length를 value로 mapping을 해준다. this.arr.length는 해당 val의 arr 내의 index를 의미한다.
여기서 this.arr.length - 1이 아니라 this.arr.length라고 해준 이유는 아직 this.arr에 val을 push하지 않았기 때문이다.
이후 val을 this.arr에 push 해준다.
중복된 요소가 들어왔을 경우에는 map.has(val)을 사용해 false를 return 해준다.

`getRandom()`

정수 형태의 값을 반환해야 하기 때문에 Math.floor로 감싸줬다.

`remove(val)`

remove 메서드를 구현하는게 어려웠다. 내가 적용한 방법은 다음과 같다.
먼저, map에 없는 요소를 삭제하려 하는 경우에는 false를 return 한다.
이후, 삭제될 인덱스(=deletedIndex)를 가져온다. this.map.get(val)
그리고 this.arr의 삭제될 인덱스에 해당하는 요소를 요소 맨 끝 값으로 치환한다.(시간복잡도 O(1)으로 구현해야 하기 때문) 이렇게 되었을 때, 현재 this.arr에는 this.arr[deletedIndex]와 this.arr[this.arr.length - 1], 즉 this.arr의 끝 요소가 중복되는 요소일 것이다.
this.map.set을 이용해 치환된 this.arr[deletedIndex](원래 this.arr의 끝에 있던 요소)가 deletedIndex val값을 가지게 된다. 이 말은, 원래는 this.arr[deletedIndex] 이 값은 this.arr의 맨 끝의 인덱스를 mapping하고 있었는데, 현재는 deletedIndex를 mapping하고 있다는 의미가 된다.
이제 arr와 map의 값을 모두 바꿨으니 map.delete(val)을 이용해 들어온 val에 해당하는 key를 map에서 찾아서 지워주고, arr는 끝 요소와 치환했기 때문에, 끝 요소는 더 이상 필요가 없기에 pop()을 통해 제거해준다.