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

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

Insert Delete GetRandom O(1) - LeetCode

문제 유형 : OOP / 배열

문제 난이도 : 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 클래스를 구현하시오.

bool insert(int val)은 val 값이 없었다면 값을 삽입하고 true를, 아니면 false를 반환시키시오.

bool remove(int val)은 val 값이 있었다면 값을 삭제하고 true를, 아니면 false를 반환시키시오.

int getRandom()은 무작위 요소를 반환하여야 합니다. 각 요소는 같은 확률로 반환되어야 합니다.

 

평균적으로 O(1)의 시간복잡도를 가지게 하시오.

 

풀이

unordered_map과 vector를 이용해서 평균적으로 O(1)의 시간복잡도를 가지게 할 수 있습니다.

unordered_map은 해시 테이블 자료구조를 이용해서 빠른 데이터 참조가 가능합니다.

 

insert

해시 맵에서 데이터를 찾지 못했다면,

vector에 값을 삽입합니다.

해시 맵에 <데이터, 인덱스>의 형태로 저장합니다.

true를 반환합니다.

데이터가 기존에 있다면 false를 반환합니다.

 

remove

해시 맵에서 데이터를 찾았다면,

vector에서 값을 삭제합니다.

인덱스가 꼬이는 것을 막기 위해서, 삭제하려는 값의 인덱스를 맨 뒤의 요소의 인덱스와 바꿔서 삭세합니다.

해시 맵에서도 데이터의 값을 삭제합니다.

그 다음 true를 반환합니다.

데이터가 기존에 없다면 false를 반환합니다.

 

getRandom

무작위 인덱스를 받아옵니다.

요소의 무작위 인덱스를 반환합니다.

 

코드(C++)

데이터를 찾기 위해서 hasVal이라는 함수도 만들었습니다.

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();
    }
};