std::random_device rd;	//	(몇 배 느려진다)
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist(0, 99);
int randd = dist(mt)

Random 을 출력하는 class를 만들라고 주문했다.

class RandomizedSet {
	std::unordered_map<int, int> umap;  // pair<val, idx>
	std::vector<int> randomV;

	int vIndx;
public:
	/** Initialize your data structure here. */
	RandomizedSet() {
		vIndx = 0;
	}

	/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
	bool insert(int val) {
		if (umap.find(val) != umap.end())
			return false;
		else
		{
			umap[val] = vIndx;
			randomV.push_back(val);
			vIndx++;
			return true;
		}
	}

	/** Removes a value from the set. Returns true if the set contained the specified element. */
	bool remove(int val) {
		if (umap.find(val) != umap.end())
		{
			int idx = umap[val];
			if (idx == randomV.size() - 1)
			{
				randomV.pop_back();
				umap.erase(val);
				vIndx--;
				return true;
			}
			int lastVal = randomV.back();
			randomV[idx] = lastVal;
			randomV.pop_back();
			umap[lastVal] = idx; // map에서 val로 저장했던 idx 값도 update 해줘야 한다.
			vIndx--;
			umap.erase(val);
			return true;
		}
		else
			return false;
	}

	/** Get a random element from the set. */
	int getRandom() {
		std::random_device rd;
		std::mt19937 mt(rd());
		std::uniform_int_distribution<int> dist(0, randomV.size() - 1);
		int rand = dist(mt);

		return randomV[rand];
	}
};

Runtime: 92 ms, faster than 23.23% of C++ online submissions for Insert Delete GetRandom O(1).

Memory Usage: 22.7 MB, less than 57.61% of C++ online submissions for Insert Delete GetRandom O(1).

랜덤 출력 속도가 상당히 떨어진다고 알고 있는데 사실이었다.

예전방식으로

class RandomizedSet {
...
...
	int getRandom() {
			return randomV[rand() % randomV.size()];
		}
}

Runtime: 32 ms, faster than 98.26% of C++ online submissions for Insert Delete GetRandom O(1).

Memory Usage: 22.5 MB, less than 83.46% of C++ online submissions for Insert Delete GetRandom

빨라진 속도를 확인 가능하다.