[LeetCode C++] 1376. Time Needed to Inform All Employees

⭐️ 난이도

Medium

 

---

⭐️ 문제

https://leetcode.com/problems/time-needed-to-inform-all-employees/submissions/

Time Needed to Inform All Employees - LeetCode

회사에 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;
    }
};