[LeetCode] 381. Insert Delete GetRandom O(1) - Duplicates allowed

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

Insert Delete GetRandom O(1) - Duplicates allowed - LeetCode

Insert Delete GetRandom O(1) - Duplicates allowed

 

이전의 Insert Delete GetRandom O(1) 문제의 업그레이드 버전이다.

이전 문제를 먼저 풀고 풀길 권한다.

Insert Delete GetRandom O(1) 풀이 : https://leetcode.com/problems/insert-delete-getrandom-o1/

Insert Delete GetRandom O(1) - LeetCode

 

 

기존 문제에서 매핑만 int-int가 아닌 int-priority_queue로 바꿔주면 된다.

제거시에 pq에서 top 부분을 참조하는 것만 유의하면 된다.

나머지는 위 링크에서 기본 풀이를 참고하자.

 

전체 풀이 코드

class RandomizedCollection {
public:
    unordered_map<int, priority_queue<int>> m;
    vector<int> v;
    unordered_map<int, priority_queue<int>>::iterator iter;
    
    RandomizedCollection() {
        this->m.clear();
        this->v.clear();
    }
    
    bool insert(int val) {
        bool ret = this->m.find(val)==this->m.end();
        this->v.push_back(val);
        if (ret) {
            priority_queue<int> pq;
            pq.push((int)v.size()-1);
            this->m[val] = pq;
        }
        else this->m[val].push(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.top()] = this->v.back();
            this->v.pop_back();
            this->m[v[iter->second.top()]].pop();
            this->m[v[iter->second.top()]].push(iter->second.top());
            this->iter->second.pop();
            if (this->iter->second.empty()) this->m.erase(iter);
        }
        return ret;
    }
    
    int getRandom() {return v[random() % this->v.size()];}
};