380_ Insert Delete GetRandom O(1)

Problem

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.

Example 1:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"][], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation

RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints:

• -2^31 <= val <= 2^31 - 1
• At most 2 * 10^5 calls will be made to insert, remove, and getRandom.
• There will be at least one element in the data structure when getRandom is called.

Solution

Problem 요약

• RandomizedSet 클래스를 구현
• 다음 세 가지 연산을 평균 O(1) 시간 복잡도로 수행해야 함.
  • insert(val): val을 삽입 (이미 존재하면 False).
  • remove(val): val을 제거 (존재하지 않으면 False).
  • getRandom(): 현재 존재하는 값 중 하나를 균등한 확률로 반환.

Constraints 분석

• -2³¹ ≤ val ≤ 2³¹ - 1
  • 값의 범위가 32-bit 정수 범위이므로 자료형으로 int 사용 가능.
• 최대 200,000번의 insert, remove, getRandom 호출
  • O(N), O(log N) 알고리즘을 사용하면 시간 초과 가능성이 있음.
  • 반드시 O(1)로 처리해야 함.
• getRandom()은 항상 최소 하나의 요소가 존재할 때만 호출됨.
  • 비어있는 경우를 고려할 필요 없음.

Pseudocode

• insert(val):

  • 만약 val이 이미 존재하면 false 반환
  • 벡터의 끝에 val 추가
  • 해시맵에 (val, 현재 벡터 크기-1) 저장
  • true 반환

• remove(val):

  • 만약 val이 존재하지 않으면 false 반환
  • 제거할 값의 인덱스를 해시맵에서 가져옴
  • 벡터의 마지막 요소를 제거할 위치로 이동 (O(1) 삭제)
  • 마지막 요소의 새로운 인덱스를 해시맵에 업데이트
  • 벡터에서 마지막 요소 제거 및 해시맵에서 val 제거
  • true 반환

• getRandom():

  • 벡터의 크기 내에서 랜덤한 인덱스를 생성
  • 해당 인덱스의 값을 반환

시간/공간 복잡도 분석

• Time complexity

연산	시간복잡도	설명
insert(val)	(1)	해시맵을 통해 존재 여부 확인 후 벡터에 추가
remove(val)	O(1)	벡터의 마지막 요소와 스왑 후 삭제
getRandom()	O(1)	벡터에서 랜덤 인덱스 선택

• Space complexity: O(N)
  • 최대 N개의 정수를 저장해야 하므로 벡터와 해시맵이 각각 O(N).

Code

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cstdlib>  // rand() 사용을 위한 라이브러리

using namespace std;

class RandomizedSet {
private:
    vector<int> data;  // 저장된 값들
    unordered_map<int, int> indexMap;  // 값 -> 벡터 인덱스 매핑

public:
    RandomizedSet() {}

    bool insert(int val) {
        if (indexMap.find(val) != indexMap.end()) {
            return false;  // 이미 존재하는 값이면 삽입 불가능
        }
        indexMap[val] = data.size();  // 값의 인덱스 저장
        data.push_back(val);  // 벡터에 추가
        return true;
    }

    bool remove(int val) {
        if (indexMap.find(val) == indexMap.end()) {
            return false;  // 존재하지 않으면 제거 불가능
        }

        int idx_to_remove = indexMap[val];  // 제거할 값의 인덱스
        int last_element = data.back();  // 벡터의 마지막 요소

        // 마지막 요소를 제거할 위치로 이동
        data[idx_to_remove] = last_element;
        indexMap[last_element] = idx_to_remove;

        // 마지막 요소 제거
        data.pop_back();
        indexMap.erase(val);

        return true;
    }

    int getRandom() {
        int randomIndex = rand() % data.size();  // 랜덤한 인덱스 선택
        return data[randomIndex];
    }
};

// ✅ 테스트 코드
int main() {
    RandomizedSet randomizedSet;

    cout << randomizedSet.insert(1) << endl;   // true (1 삽입)
    cout << randomizedSet.remove(2) << endl;   // false (2 없음)
    cout << randomizedSet.insert(2) << endl;   // true (2 삽입)
    cout << randomizedSet.getRandom() << endl; // 1 또는 2 랜덤 반환
    cout << randomizedSet.remove(1) << endl;   // true (1 삭제)
    cout << randomizedSet.insert(2) << endl;   // false (2는 이미 존재)
    cout << randomizedSet.getRandom() << endl; // 2 반환 (2만 남음)

    return 0;
}