2023.06.03 Today's Challenge

fabichoi 2023. 6. 3. 23:45

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

Time Needed to Inform All Employees - LeetCode

Can you solve this real interview question? 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 th

leetcode.com

딱봐도 DFS인데, 실제 구현을 못함.
오늘부터는 구현에 대한 신경도 써야 함.
외워서라도 풀어봅시다!

class Solution:
    def dfs(self, manager, informTime, adjList):
        maxTime = 0
        for subordinate in adjList[manager]:
            maxTime = max(maxTime, self.dfs(subordinate, informTime, adjList))
        return maxTime + informTime[manager]

    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        adjList = defaultdict(list)
        for i in range(n):
            if manager[i] != -1:
                adjList[manager[i]].append(i)
        return self.dfs(headID, informTime, adjList)