380. Insert Delete GetRandom O(1)

• O(1)으로 mapping을 구성함과 동시에 random access를 수행할 수 있는 방법에 대해서 묻는 문제이다.
• 두 가지 자료구조를 조합하여 해결하는 문제이다.

• 처음에는 직접 Node를 구현해서 hash map과 linked list를 활용해서 풀었었다.
• 하지만 getRandom 구현에서 linked list를 random access 할 수가 없어서 문제가 되었다.

• 생각해보니 insert/delete를 O(1)에 하려면 unordered_map 을 쓰면 되는 거였다.
• 문제는 random access도 같이 제공해야 되므로 실제 값은 vector에 위치해야 한다는 문제가 있었다.
• 결국 다른 사람의 솔루션을 참고했는데 unordered_map에는 vector 상의 위치를 저장하고 vector에는 실제 값을 저장하는 방식으로 해결했다.
• 삭제할 때는 (1) 삭제하는 값과 vector의 마지막 값을 swap하고 (2)vector에서 마지막 항목을 제거 vector::pop_back() (3) unordered_map에서 swap된 값의 위치를 update하는 방식을 취한다.

class RandomizedSet {
public:
    RandomizedSet()
        : positions(),
          values() {
    }
    
    bool insert(int val) {
        auto itr = positions.find(val);
        if (itr != positions.end()) return false;
        int pos = values.size();
        values.push_back(val);
        positions[val] = pos;
        return true;
    }
    
    bool remove(int val) {
        auto itr = positions.find(val);
        if (itr == positions.end()) return false;
        int pos = itr->second;
        int lastVal = values[values.size() - 1];
        // swap last element to removed position
        values[pos] = lastVal;
        positions[lastVal] = pos;
        // remove element & pos
        values.pop_back();
        positions.erase(itr);
        return true;
    }
    
    int getRandom() {
        int index = rand() % values.size();
        return values[index];
    }

private:
    unordered_map<int, int> positions;
    vector<int> values;
};