[LeetCode/Medium] 398. Random Pick Index

목표: 배열에서 특정 수의 인덱스를 랜덤으로 반환해주는 클래스 구현

- 생성자

- pick()

 

1. Input

- 생성자: int[] nums

- pick(): int target

 

2. Output

- pick(): nums에서 target의 인덱스 중 1개를 랜덤으로 반환

// 인덱스가 여러 개일 경우, 각 인덱스가 선택될 확률은 모두 같다.

 

3. Constraint

1) 1 <= nums.length <= 2 * 10^4

2) - 2^31 <= nums[i] <= 2^31 - 1

3) target은 nums의 요소 중 1개이다.

4) pick()은 최대 10^4번 호출된다.

 

4. Example

Solution solution = new Solution([1, 2, 3, 3, 3]); // 배열 [1,2,3,3,3]을 받는다.
solution.pick(3); // 3의 인덱스인 2,3,4 중 1개를 랜덤으로 반환
solution.pick(1); // 1의 인덱스인 0을 반환

 

5. Code

1) 첫 코드(2023/02/16)

class Solution {
    int[] deck;

    public Solution(int[] nums) {
        deck = nums;    
    }
    
    public int pick(int target) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i=0 ; i<deck.length ; i++){
            if(deck[i]==target)
                list.add(i);
        }
        if(list.size()==1) return list.get(0);
        else return list.get((int)(Math.random()*list.size()));
    }
}