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

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

Insert Delete GetRandom O(1) - LeetCode

leetcode - Insert Delete GetRandom O(1)

문제 유형 : 해시, 구현

문제 난이도 : Medium

 

문제

Implement the RandomizedSet class:

• RandomizedSet() Initializes the RandomizedSet object.
• bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
• bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
• int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

 

RandomizedSet 클래스를 구현하시오:

• RandomizedSet()은 RandomizedSet 객체를 초기화합니다.
• bool insert(int val)은 val이 없는 경우 val을 삽입합니다. 삽입에 성공하면 true, 아니면 false를 반환합니다.
• bool remove(int val)은 val이 있는 경우 val을 제거합니다. 제거에 성공하면 true, 아니면 false를 반환합니다.
• int getRandom() 은 현재 요소들 중에서 무작위 요소를 반환합니다.

 

당신은 평균 O(1)의 시간 복잡도로 구현해야 합니다.

 

 

풀이

요소를 담는 배열과, 요소의 인덱스를 담는 map을 만듭니다.

 

insert: 만약 값이 없다면, 배열의 맨 뒤에 요소를 추가하고, 인덱스를 저장시킵니다.

remove: 만약 값이 있다면, 맨 뒤에 있는 요소와 배열에서의 위치를 바꾸고(여기서 map에 저장된 인덱스도 바꿉니다), 배열의 맨 뒤를 제거합니다.

getRandom: 랜덤 난수를 생성하여 배열의 크기만큼 나눠줍니다.

 

코드

C++

class RandomizedSet {
private:
    vector<int> elements;
    unordered_map<int, int> indexMap;

public:
    RandomizedSet() {
    }

    bool insert(int val) {
        if (!hasVal(val)) {
            elements.push_back(val);
            indexMap[val] = elements.size() - 1;
            return true;
        } else {
            return false;
        }
    }

    bool remove(int val) {
        if (hasVal(val)) {
            int lastElement = elements.back();
            int valIndex = indexMap[val];

            elements[valIndex] = lastElement;
            elements.pop_back();

            indexMap[lastElement] = valIndex;
            indexMap.erase(val);

            return true;
        } else {
            return false;
        }
    }

    int getRandom() {
        int randomIndex = rand() % elements.size();

        return elements[randomIndex];
    }

    bool hasVal(int val){
        return indexMap.find(val) != indexMap.end();
    }
};