[LeetCode] 380. Insert Delete GetRandom O(1)

문제 출처: https://leetcode.com/problems/insert-delete-getrandom-o1/

Insert Delete GetRandom O(1) - LeetCode

---

문제

RandomizedSet 클래스를 구현하라:

• RandomizedSet(): RandomizedSet 객체를 초기화한다.
• bool insert(int val): 집합 자료구조에 아이템 val이 존재하지 않을 때 추가한다. 만약 아이템이 존재하지 않았다면 true를 반환하고, 존재했다면 false를 반환한다.
• bool remove(int val): 집합 자료구조에 아이템 val이 존재한다면 제거한다. 만약 아이템이 존재했다면 true를 반환하라고, 존재하지 않았다면 false를 반환한다.
• int getRandom(): 현재 집합 자료구조에 있는 원소 중 하나를 랜덤 하게 반환한다(이 메서드가 호출될 때, 최소 한 개의 원소는 자료구조 내에 있음이 보장된다). 각 원소가 반환될 확률은 동일해야 한다.

 

위의 모든 함수는 평균 O(1) 시간 복잡도를 갖도록 구현해야 한다.

예제

Input:
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output: [null, true, false, true, 2, true, false, 2]

Explanation:
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

---

풀이

배열(Array)과 맵(Map) 자료구조를 활용하여 문제를 해결할 수 있습니다. 두 자료구조는 아래와 같은 특성을 갖기 때문에 이 문제를 해결함에 있어 유용하게 쓰일 수 있습니다.

• Map
  • 빠른 삽입, 삭제 연산 가능
  • 빠른 원소 찾기 가능
• Array
  • 배열의 맨 뒤에서 삽입과 삭제 시, 빠르게 가능
  • 특정 인덱스의 위치에 빠르게 접근 가능

먼저 맵을 이용하여 의사 코드를 작성해보면 다음과 같습니다. 아래의 코드는 자바스크립트 문법을 기반으로 작성한 의사 코드이며 "...(줄임표)"로 표시한 부분은 아직 어떤 값(혹은 코드)가 작성될지 정해지지 않은 곳입니다.

class RandomizedSet {
    #map;
    
    constructor() {
    	this.map = new Map();
    }
    
    insert = (val) => {
    	if (this.map.has(val)) { return false; }
        this.map.set(val, ...);
        return true;
    }
    
    remove = (val) => {
    	if (!this.map.has(val)) { return false; }
        this.map.delete(val);
        return true;
    }
    
    getRandom() {
    	...
    }
}

이와 같이 맵을 이용하게 되면, insert와 remove 연산을 O(1)의 시간 안에 할 수 있습니다. 하지만 getRandom 연산은 O(1)에 불가능합니다. 이때 필요한 게 배열입니다.

 

배열에도 삽입과 삭제 요청에 따라 값을 저장하고 삭제합니다. 단, 배열은 마지막 위치에서 삽입과 삭제 연산이 O(1)이기 때문에 삭제할 값과 배열의 마지막 원소의 값의 위치를 바꿔 삭제할 원소가 항상 마지막에 있어야 합니다.

 

문제는 배열만으로는 어떤 값이 어느 인덱스에 있는지 알려고 한다면 배열을 순회해야 합니다. 즉 O(N)의 시간이 걸립니다. 여기에서 맵 자료구조의 진가가 드러납니다. 맵을 이용해서 삭제하고자 하는 값이 어떤 인덱스에 저장되어 있는지 빠르게 찾아낼 수 있도록 한다면 배열이 가진 한계를 극복할 수 있습니다.

class RandomizedSet {
    #map;
    #arr;
    
    constructor() {
    	this.map = new Map();
        this.arr = [];
    }
    
    insert = (val) => {
    	if (this.map.has(val)) { return false; }
        
        // val이 저장된 위치를 map에 저장
        this.map.set(val, this.arr.length);
        this.arr.push(val);
        
        return true;
    }
    
    remove = (val) => {
    	if (!this.map.has(val)) { return false; }
        
        // 배열의 마지막 원소와 삭제할 원소를 swap
        const idx = this.map.get(val);
        [this.arr[idx], this.arr[this.arr.length-1]] = [this.arr[this.arr.length-1], this.arr[idx]];
        
        // map에 설정되어 있는 인덱스 재설정
        this.map.set(arr[idx], idx);
        
        // arr, map에서 제거
        this.arr.pop();
        this.map.delete(val);
        
        return true;
    }
    
    getRandom() {
    	...
    }
}

이제 배열의 특징을 활용하여 getRandom()을 손쉽게 구현할 수 있습니다. 배열은 맵과 달리 위치 정보를 통해 접근이 가능하므로 0 ~ N-1 (N=배열의 크기) 사이의 정수를 생성하는 것으로 원하는 것을 이룰 수 있습니다.

class RandomizedSet {
    #map;
    #arr;
    
    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; }
        
        const idx = this.map.get(val);
        [this.arr[idx], this.arr[this.arr.length-1]] = [this.arr[this.arr.length-1], this.arr[idx]];
        this.map.set(this.arr[idx], idx);
        this.arr.pop();
        this.map.delete(val);
        
        return true;
    }
    
    getRandom = () => {
    	return this.arr[Math.floor(Math.random() * this.arr.length)]
    }
}

 

Github: 380.js

GitHub - opwe37/Algorithm-Study