리트코드 - 398. Random Pick Index

리트코드 - 398. Random Pick Index

주어진 nums에 대해, nums의 원소를 pick하면 그 index를 return하는 문제입니다. nums에 중복된 원소가 있는 경우, 해당 index들이 동일한 확률로 return되어야 하며, 이를 구현하는 Solution class를 작성하는 문제입니다. 중복된 원소들의 index를 해결하기 위해 dictionary를 사용했습니다. 모든 nums의 원소에 대해 list를 만들어 index들을 저장합니다. target에 대한 value인 list를 꺼내어, 0부터 list의 size까지 임의로 추출한 숫자를 list의 index로 쓰면, 동일한 확률로 알맞는 index를 꺼낼 수 있습니다.

참고 )
pick method에는 target만 넘어가기 때문에 dictionary를 인스턴스 변수로 선언했습니다. 그런데 이때 무심결에 static을 붙여 클래스 변수로 만들었는데, 그러면 오류가 납니다. dictionary에, 이전 testcase에 있던 nums[i]들에 대한 오만가지 index들이 저장되어 있습니다.

import java.util.*;

class Solution {

    HashMap<Integer, ArrayList<Integer>> hashMap = new HashMap<>();

    public Solution(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            ArrayList<Integer> cur = hashMap.get(nums[i]);
            if (cur == null) {
                cur = new ArrayList<>();
            }
            cur.add(i);
            hashMap.put(nums[i], cur);
        }
    }
    
    public int pick(int target) {
        ArrayList<Integer> cur = hashMap.get(target);
        int pick = (int) (cur.size() * Math.random());

        return cur.get(pick);
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */