[Algorithm] LeetCode - 1817. Finding the Users Active Minutes(Hash)

 

LeetCode 문제입니다.

[문제설명]

You are given the logs for users' actions on LeetCode, and an integer k. The logs are represented by a 2D integer array logs where each logs[i] = [IDi, timei] indicates that the user with IDiperformed an action at the minute timei.

Multiple users can perform actions simultaneously, and a single user can perform multiple actionsin the same minute.

The user active minutes (UAM) for a given user is defined as the number of unique minutes in which the user performed an action on LeetCode. A minute can only be counted once, even if multiple actions occur during it.

You are to calculate a 1-indexed array answer of size k such that, for each j (1 <= j <= k), answer[j] is the number of users whose UAM equals j.

Return the array answer as described above.

 

번역)

LeetCode에 대한 사용자의 작업에 대한 로그와 정수 k가 제공됩니다.
로그는 2D 정수 배열 로그로 표시되며, 여기서 각 logs[i] = [IDi, timei]는 IDi를 가진 사용자가 분 시간i에 작업을 수행했음을 나타냅니다.
여러 사용자가 동시에 작업을 수행할 수 있으며 단일 사용자는 같은 1분에 여러 작업을 수행할 수 있습니다.

지정된 사용자의 UAM(사용자 활동 시간)은 사용자가 LeetCode에서 작업을 수행한 고유한 시간(분)으로 정의됩니다.
1분은 그 동안 여러 동작이 발생하더라도 한 번만 계산할 수 있습니다.

각 j(1 <= j <= k)에 대해 answer[j]가 UAM이 j와 같은 사용자의 수가 되도록 크기가 k인 1-인덱싱된 배열 응답을 계산해야 합니다.

위에서 설명한 대로 배열 응답을 반환합니다.

 

Topic: Array, Hash Table

Level: Medium

Accepted 28,369 / Submissions 35,281

---

[제한사항]

• 1 <= logs.length <= 104
• 0 <= IDi <= 109
• 1 <= timei <= 105
• k is in the range [The maximum UAM for a user, 105].

---

[입출력]

예시 1

 

Input: logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5
Output: [0,2,0,0,0]
Explanation:
The user with ID=0 performed actions at minutes 5, 2, and 5 again. Hence, they have a UAM of 2 (minute 5 is only counted once).
The user with ID=1 performed actions at minutes 2 and 3. Hence, they have a UAM of 2.
Since both users have a UAM of 2, answer[2] is 2, and the remaining answer[j] values are 0.

 

예시 2

Input: logs = [[1,1],[2,2],[2,3]], k = 4
Output: [1,1,0,0]
Explanation:
The user with ID=1 performed a single action at minute 1. Hence, they have a UAM of 1.
The user with ID=2 performed actions at minutes 2 and 3. Hence, they have a UAM of 2.
There is one user with a UAM of 1 and one with a UAM of 2.
Hence, answer[1] = 1, answer[2] = 1, and the remaining values are 0.

---

[문제풀이]

/**
 * @param {number[][]} logs
 * @param {number} k
 * @return {number[]}
 */
var findingUsersActiveMinutes = function(logs, k) {
    let result = Array(k).fill(0)
    let uam = logs.reduce((acc, cur) => {
        const [uId, uAction] = cur
        
        if (!acc[uId]) acc[uId] = new Set([uAction])
        else acc[uId].add(uAction)
        return acc
    }, {})
    
    
    Object.values(uam).forEach(uamItem => {
        uniqSize = uamItem.size
        result[uniqSize-1]++
    })
    
    return result
};

 

Idea: 

1. left child node부터 dfs 함수 call 

2. Leaf node이고 targetSum과 경로상 노드들의 합이 같다면 anwer push

3. 아니라면 dfs call

---

[Performance]