티스토리 뷰
728x90
반응형
Problem
Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.
Implement the Solution class:
Solution(ListNode head) Initializes the object with the integer array nums.
int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen.
Example 1:
Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]
Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
Constraints:
- The number of nodes in the linked list will be in the range [1, 10^4].
- -10^4 <= Node.val <= 10^4
- At most 10^4 calls will be made to getRandom.
Follow up:
What if the linked list is extremely large and its length is unknown to you?
Could you solve this efficiently without using extra space?
Solution
LinkedList가 주어졌을 때 랜덤으로 노드의 값을 반환하는 기능을 구현하는 문제입니다.
예전에 쿠팡 라이브 코딩테스트 볼 때 유사한 문제를 풀었던 기억이 있는데, 그 때 가장 중요하게 취급했던 부분은 시간, 공간 복잡도였으니 이런 문제를 풀 때 한 번 쯤 고려해 볼 만한 것 같습니다.
Map을 사용하여 간단히 구현하였습니다.
import io.lcalmsky.leetcode.ListNode;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class Solution {
private final Map<Integer, ListNode> map;
private final Random random;
public Solution(ListNode head) {
map = new HashMap<>();
random = new Random();
int i = 0;
while (head != null) {
map.put(i++, head);
head = head.next;
}
}
public int getRandom() {
return map.get(random.nextInt(map.size())).val;
}
}
Test
package io.lcalmsky.leetcode.linked_list_random_node;
import static org.junit.jupiter.api.Assertions.assertTrue;
import io.lcalmsky.leetcode.ListNode;
import java.util.List;
import org.junit.jupiter.api.Test;
class SolutionTest {
@Test
void test() {
Solution solution = new Solution(ListNode.of(1, 2, 3));
List<Integer> list = List.of(1, 2, 3);
assertTrue(list.contains(solution.getRandom()));
assertTrue(list.contains(solution.getRandom()));
assertTrue(list.contains(solution.getRandom()));
}
}
728x90
반응형
'Algorithm > LeetCode Daily Challenge' 카테고리의 다른 글
1041. Robot Bounded In Circle (0) | 2022.01.10 |
---|---|
1463. Cherry Pickup II (0) | 2022.01.09 |
382. Linked List Random Node (0) | 2022.01.08 |
1094. Car Pooling (0) | 2022.01.07 |
131. Palindrome Partitioning (0) | 2022.01.06 |
1009. Complement of Base 10 Integer (0) | 2022.01.05 |
댓글
공지사항
- Total
- 71,740
- Today
- 103
- Yesterday
- 133
링크
TAG
- Linux
- 스프링 부트
- QueryDSL
- 스프링 부트 회원 가입
- Spring Boot
- Jackson
- 스프링부트
- JSON
- 스프링 부트 애플리케이션
- 알고리즘
- 스프링 데이터 jpa
- leetcode
- 스프링 부트 jwt
- gRPC
- r
- leetcode binary search
- spring boot application
- Java
- intellij
- spring boot app
- 스프링 부트 웹 애플리케이션
- Spring Data JPA
- JPA
- spring boot jwt
- Spring Boot Tutorial
- leetcode stack
- proto3
- 도메인 설계
- leetcode bst
- 스프링 부트 튜토리얼