[LeetCode/Easy] 382. Linked List Random Node

목표: 링크드 리스트의 노드값을 랜덤으로 돌려주는 Solution클래스 구현

- 생성자

- getRandom()

 

1. Input

- 생성자: 링크드 리스트

- getRandom(): 없음

 

2. Output

- getRandom(): 링크드 리스트의 노드값 중 하나

// 모든 노드들이 선택 받을 확률은 다 같아야 한다.

 

3. Constraint

1) 리스트에 포함된 노드의 수의 범위는 [1, 10^4]의 정수이다.

2) - 10^4 <= Node.val <= 10^4

3) getRandom()은 최대 10^4번까지 호출된다.

 

4. Example

Solution solution = new Solution([1, 2, 3]); // 리스트의 노드를 받는다.
// getRandom()을 호출하면 1, 2, 3 중 1개를 랜덤으로 반환한다.
solution.getRandom(); // 1
solution.getRandom(); // 3
solution.getRandom(); // 2
solution.getRandom(); // 3
solution.getRandom(); // 3

 

5. Code

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

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
    ArrayList<Integer> list;
    
    public Solution(ListNode head) {
        list = new ArrayList<Integer>();
        while(head!=null){
            list.add(head.val);
            head = head.next;
        }
    }

    public int getRandom() {
        return list.get((int)(Math.random()*list.size()));
    }
}