LeetCode日本語修行18日目- [690-社員の重要性]


Employee Importance

参考:https://leetcode.com/problems/employee-importance/

問題の内容:

従業員情報のDBの中に、従業員の固有ID、重要度の値、直属の部下のIDが含まれています。
例えば、従業員1は従業員2のリーダーであり、従業員2は従業員3のリーダーであり、それぞれ重要度の値が15、10、5であるとします。すると、社員1は[1, 15, [2]]、社員2は[2, 10, [3]]、社員3は[3, 5, []]のようなデータ構造になります。なお、従業員3は従業員1の部下でもありますが、関係は直接的ではありません。
さて、会社の従業員情報と従業員IDがあれば、この従業員とその部下全員の重要度の合計値を返す必要があります。

例:

例1:
Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11
Explanation:
従業員1の重要度は5で、彼には2人の直属の部下、従業員2と従業員3がいます。つまり、社員1の重要度の合計は、5+3+3=11となります。

ヒント:

1.One employee has at most one direct leader and may have several subordinates.
2.The maximum number of employees won't exceed 2000.


普通の深さ優先探索を使って解決できます。

/*
 *  // Definition for Employee.
 *  class Employee {
 *      var id:Int = 0
 *      var importance:Int = 0
 *      var subordinates:List<Int> = listOf()
 *  }
 */

class Solution {
    var map = HashMap<Int, Employee>()
    fun getImportance(employees: List<Employee?>, id: Int): Int {
        for ( employee in employees) {
            map[employee!!.id] = employee
        }
        return dfs(id);
    }
    private fun  dfs(id : Int) : Int {
        var employee = map[id];
        var total = employee!!.importance;
        var subordinates = employee.subordinates;
        for (subId in subordinates) {
            total += dfs(subId);
        }
        return total;
    }
}