[C#] 1376. Time Needed to Inform All Employees

 

1. 문제

 

회사에는 0부터 n-1까지 고유한 ID를 가진 직원 n명이 있다.

회사 대표는 headID를 가진 한 명이다.

 

각 직원은 한 명의 직속 관리자가 있고 manager array로 주어진다. i번째 직원의 직속 관리자는 manager[i]이다.

회사 대표의 직속 관리자는 -1이다. 또한 종속 관계가 트리 구조임을 보장한다.

 

회사 대표는 모든 직원에게 긴급 뉴스를 알리길 바란다. 대표는 그의 직속 부하들에게 알릴 것이고 직속 부하들은 그들의 부하들에게 알릴 것이다. 모든 직원이 긴급 뉴스를 알게 될 때까지 계속된다.

 

i번째 직원은 그의 모든 직속 부하에게 알리는 데 informTime[i]분이 걸린다.

 

모든 직원이 긴급 뉴스를 알게 되는 데 걸리는 시간을 리턴하면 된다.

 

 

 

---

 

2. 풀이 과정

 

트리 구조이므로 자식을 따라가면서 시간을 더하고, 사장부터 모든 말단직원까지의 소요 시간 중 가장 큰 값을 리턴하면 될 것 같았으나 각 직원이 부하직원의 정보를 갖고 있는 게 아니라 상관의 정보를 갖고 있기 때문에 거꾸로 올라가기로 했다.

 

manager[i]가 -1이 아니라면 (상관이 있다면) i를 manager[i]로 바꿔가면서 상관을 계속 따라간다.

따라가면서 상관의 전파 시간을 임시 변수에 저장.

사장까지 도달했다면 임시 총 전파시간을 현재까지의 최대 전파시간과 비교하여 최대 전파시간을 갱신.

 

...

 

최대한 코드를 빨리 짜는데 집중해서 성능은 고려하지 못했다.

여건이 된다면 후에 개선해 보는 걸로...

 

public class Solution {
    public int NumOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        var result = 0;

        for(int i = 0; i < n; ++i)
        {
            int tmpResult = 0;
            int parentIdx = manager[i];
            while(parentIdx > -1)
            {
                tmpResult += informTime[parentIdx];
                parentIdx = manager[parentIdx];
            }

            result = Math.Max(result, tmpResult);
        }

        return result;
    }
}