⭐️ 난이도
Medium
⭐️ 문제
https://leetcode.com/problems/time-needed-to-inform-all-employees/submissions/
회사에 n명의 직원이 있고, 각각의 직원에게는 0 ~ n-1까지 고유 ID가 있다. CEO만 headID를 가지고 있다.
각 직원에게는 manager가 있는데, manager 배열로 주어진다.
manager[i]는 i-1번째 직원의 직속 manager라는 뜻이다. manager[headID] = -1이다.
또한 부하 직원과의 관계는 트리 구조를 가진다고 가정한다.
CEO는 회사의 무슨 직원에게 급한 소식을 전하려고 한다.
CEO가 자신의 직속 부하에게 이야기하면, 모든 직원들이 소식을 다 알 때까지 자신의 직속 부하에게 소식을 전할 것이다.
i번째 직원은 그의 모든 직속 부하에게 소식을 전하기 위해서는 informTime[i]의 시간이 필요하다.
(즉, infromTime[i]의 시간이 지나고나면 그의 모든 직속 부하들이 소식을 전할 것이다.)
모든 직원에게 소식을 전달하려고 할 때, 시간이 얼마나 필요한지 구하라.
⭐️ Follow-up
X
⭐️ Idea flow
정보가 주어지는 형태를 먼저 살펴보면 manager과 informTime은 vector 컨테이너로, headID와 n은 int형 변수로 주어진다.
그럼 각각의 변수가 의미하는 바는 무엇일까?
1) headID : 루트 노드의 번호
2) manager[i] = k : i번째 노드의 부모 노드는 k이다. k = -1이라면 i가 head
3) informTime : 자신의 직속 상사와의 가중치 정보
트리 구조로 이어져있으니 manager에서 주어진 정보를 이용하여 계속 자식 노드로 이동하면 될 것이다.
headID에서부터 시작해서 자식 노드로 타고 들어가려 했지만, 그렇게 하려면 manager를 계속 for문으로 돌면서 원하는 값을 찾아야 한다.
이렇게 하면 시간 복잡도면에서 너무 비 효율적이다.
따라서 unordered_map<int, vector<int>> hashmap을 선언하여 manager에 담겨있는 부모-자식 정보를 저장하고 이를 이용하는 것이 더 효율적일 것이다.
전체적인 알고리즘
1) unordered_map을 선언하여 manager에 담겨 있는 부모-자식 정보 저장
2) 루트 노드에서 BFS를 시작하여 한 단계가 지날 때마다 informTime(시간) 값을 더해준다.
3) 단계를 진행하면서 시간의 최대 값을 갱신
4) 최대 값을 반환
시간과 메모리 사용량은 위와 같이 나왔다!
⭐️ Code
class Solution {
public:
int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
int result = 0;
unordered_map<int, vector<int>> hashmap;
for(int i = 0; i < manager.size(); i++){
hashmap[manager[i]].emplace_back(i);
}
queue<pair<int, int>> q;
q.push({headID, 0});
while(!q.empty()){
int cur = q.front().first;
int time = q.front().second;
q.pop();
result = max(result, time);
for(int i = 0; i < hashmap[cur].size(); i++){
int next = hashmap[cur][i];
int next_time = time + informTime[cur];
q.push({next, next_time});
}
}
return result;
}
};