[LeetCode] 398. Random Pick Index

https://leetcode.com/problems/random-pick-index/

Random Pick Index - LeetCode

Random Pick Index - Medium

처음에 배열이 넣어지고, 배열에 있는 수를 가지고 pick 을 하면, 배열내에서 그 수가 해당하는 index를 random으로 리턴하는 문제이다.

상당히 간단하다.

처음 배열에 넣어질때, map을 하나 만들어 

{ 수 : [인덱스들] } 의 꼴로 매핑시켜주면 된다.

그 후 pick을 하면 map에서 수를 불러 얻은 인덱스 벡터에서 랜덤으로 하나 뽑아주자.

삽입/삭제가 없어 쉬운 문제다.

 

전체 풀이 코드

 

class Solution {
public:
    unordered_map<int, vector<int>> m;
    Solution(vector<int>& nums) {
        m.clear();
        for (int i=0; i<nums.size(); i++) {
            if (m.find(nums[i])==m.end()) m[nums[i]] = {};
            m[nums[i]].push_back(i);
        }
    }
    int pick(int target) {return m[target][rand() % m[target].size()];}
};