[Medium] 1376. Time Needed to Inform All Employees

문제

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company is the one with headID.

Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager, [headID] = -1. Also, it is guaranteed that the subordination relationships have a tree structure.

The head of the company wants to inform all the company employees of an urgent piece of news. He will inform his direct subordinates, and they will inform their subordinates, and so on until all employees know about the urgent news.

The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e., After informTime[i] minutes, all his direct subordinates can start spreading the news).

Return the number of minutes needed to inform all the employees about the urgent news.

 

A 회사에는 0부터 n - 1까지의 직원마다 고유 ID를 가진 직원이 있습니다. 회사 대표는 headID가 있는 사람이다.
각 직원은 관리자 배열에 한 명의 직속 관리자가 있으며, 여기서 관리자[i]는 두 번째 직원인 관리자[head]의 직속 관리자입니다. 또한, 종속 관계가 트리 구조를 갖는 것이 보장된다. 
그 회사의 대표는 모든 회사 직원들에게 긴급한 소식을 알리고 싶어 한다. 그는 직속 부하에게 알릴 것이고, 부하들은 모든 직원들이 긴급한 소식을 알 때까지 그들의 부하들에게 알릴 것이다. 
i번째 직원은 정보가 필요합니다.모든 직속 부하에게 알릴 시간 [i]분 (예: 통보 후) 시간이 지나면 그의 직속 부하들이 모두 그 소식을 퍼뜨리기 시작할 수 있다.
모든 직원에게 긴급 소식을 알리는 데 필요한 시간(분)을 반환합니다.

 

예시

Example 1:

Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Explanation: The head of the company is the only employee in the company.

Example 2:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

 

제약 조건

Constraints:

• 1 <= n <= 105
• 0 <= headID < n
• manager.length == n
• 0 <= manager[i] < n
• manager[headID] == -1
• informTime.length == n
• 0 <= informTime[i] <= 1000
• informTime[i] == 0 if employee i has no subordinates.
• It is guaranteed that all the employees can be informed.

 

풀이 과정

discuss를 참조하여 문제를 해결하였다.

 

employees 라는 map을 만들어 인덱스와 빈 배열(트리 값이 들어갈 자리)을 생성한다.

for문을 돌며 headID가 아닌 요소들을 map의 빈 배열에 push한다.

dfs 함수를 실행한다.

dfs 함수는 employess의 head값을 가지고 온 뒤, dfs 함수를 재귀호출 한다. 이 때 informTime[head]를 더하여 제일 긴 시간을 return한다.

 

풀이 코드

/**
 * @param {number} n
 * @param {number} headID
 * @param {number[]} manager
 * @param {number[]} informTime
 * @return {number}
 */
var numOfMinutes = function(n, headID, manager, informTime) {
  let employees = new Map(Array.from(manager, (_, i) => [i, []]));

  for (const [i, head] of manager.entries()) {
    if (head !== -1) {
      employees.get(head).push(i);
    }
  }
    
  return dfs(headID);

  function dfs(head) {
    return Math.max(0, ...employees.get(head).map(dfs)) + informTime[head];
  }  
};