[99클럽 코테 스터디 25일차 TIL] Random Pick Index

💡문제

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

398. Random Pick Index

Given an integer array nums with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Implement the Solution class:

• Solution(int[] nums) Initializes the object with the array nums.
• int pick(int target) Picks a random index i from nums where nums[i] == target. If there are multiple valid i's, then each index should have an equal probability of returning.

Example 1:

Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

Explanation
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(1); // It should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.

Constraints:

• 1 <= nums.length <= 2 * 104
• 231 <= nums[i] <= 231 - 1
• target is an integer from nums.
• At most 104 calls will be made to pick.

 

💡키워드

• 그래프

 

💡접근/해결 방법

✅ 풀이

from collections import defaultdict
from typing import List

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # Build the graph
        graph = defaultdict(dict)
        for (x, y), value in zip(equations, values):
            graph[x][y] = value
            graph[y][x] = 1 / value

        def dfs(x: str, y: str, visited: set) -> float:
            if x not in graph or y not in graph:
                return -1.0
            if x == y:
                return 1.0
            visited.add(x)
            for neighbor in graph[x]:
                if neighbor not in visited:
                    result = dfs(neighbor, y, visited)
                    if result != -1.0:
                        return result * graph[x][neighbor]
            visited.remove(x)
            return -1.0

        # Process queries
        results = []
        for query in queries:
            results.append(dfs(query[0], query[1], set()))

        return results