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

https://leetcode.com/problems/insert-delete-getrandom-o1/

Insert Delete GetRandom O(1) - LeetCode

Insert Delete GetRandom O(1)

 

아래 기능을 하는 class를 구현하는 문제다.

1. RandomizedSet : 클래스를 초기화한다.

2. insert : 클래스에 들어온 val을 저장한다. 이때, 이미 저장되어 있다면 false를, 없다면 true를 리턴한다.

3. remove : 클래스에서 val을 삭제한다. 이때, 값이 있다면 true를, 없다면 false를 리턴한다.

4. getRandom : 저장된 val들을 랜덤으로 하나 출력한다.

 

set이나 map을 이용해 풀이하면 된다.

unordered map으로 hash map을 선언하고,

random 출력에서의 편이를 위해 vector도 하나 선언한다.

 

insert 시에는 map의 find를 통해 true, false를 결정하고, vector에도 추가해준다.

그 후, map에는 vector에서의 index를 매핑한다.

 

remove 시에는 map의 find를 통해 역시 true, false를 결정한다.

그 다음이 중요하다.

먼저 map에서 해당 val의 index를 꺼낸다.

vector에서 그 index를 참조하고, vector의 가장 뒤에 있는 값으로 바꾼다.

vector의 가장 뒤 값을 pop으로 제거하면 실질적으로 우리가 원하는 val이 지워진다.

마지막으로 map에서 원래 가장 뒤 값이었던 값과 참조한 index를 매핑해주고, val 은 map에서 지워준다.

 

getRandom 시에는 vector에서 random 함수를 통해 아무거나 꺼내준다.

 

전체 풀이 코드

class RandomizedSet {
public:
    unordered_map<int, int> m;
    vector<int> v;
    unordered_map<int, int>::iterator iter;
    
    RandomizedSet() {
        this->m.clear();
        this->v.clear();
    }
    
    bool insert(int val) {
        bool ret = this->m.find(val)==this->m.end();
        if (ret) {
            this->v.push_back(val);
            this->m[val] = v.size()-1;
        }
        return ret;
    }
    
    bool remove(int val) {
        this->iter = this->m.find(val);
        bool ret = this->iter!=this->m.end();
        if (ret) {
            this->v[iter->second] = this->v.back();
            this->v.pop_back();
            this->m[v[iter->second]] = iter->second;
            this->m.erase(iter);
        }
        return ret;
    }
    
    int getRandom() {return v[random() % this->v.size()];}
};