690. Employee Importance

#HashTable #DFS #BFS

 

직원의 고유 ID와 중요도, 부하 직원의 ID를 포함한 직원 정보의 데이터 구조가 있다.

직원 배열 employees는 다음의 특징을 가진다.

- employees[i].id 는 i번째 직원의 ID이다.
- employees[i].importance 는 i번째 직원의 중요도 값이다.
- employees[i].subsciates 는 i번째 직원의 부하 직원 ID 의 목록이다.

직원의 ID를 나타내는 id가 주어졌을 때 이 직원과 모든 직간접적인 부하 직원의 총 중요도 값을 반환한다.

---

Trial 1 : Java, 21/02/19

/*
// Definition for Employee.
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
};
*/

class Solution {
    Map<Integer, Employee> map;
    public int getImportance(List<Employee> employees, int id) {
        int sum = 0;
        
        if(employees==null)
            return 0;
        
        map = new HashMap<>();
        for(int i=0; i<employees.size(); i++) {
            map.put(employees.get(i).id, employees.get(i));
        }
        
        if(!map.containsKey(id))
            return 0;
        
        return dfs(id);
    }
    
    public int dfs(int id) {
        Employee emp = map.get(id);
        int sum = emp.importance;
        for(int j=0; j<emp.subordinates.size(); j++) {
            sum += dfs(emp.subordinates.get(j));
        }
        
        return sum;
    }
}

풀이:

추후 정리 예정

 

리뷰: 

런타임 98.91%, 메모리 98.87% 의 성능으로 예전에 자바 언어로 풀었던 DFS 문제이다.

Hash Map을 함께 사용하는 문제였고 카테고리에는 BFS 도 함께 있었지만 DFS 로 풀어보았다.

아직 파이썬으로는 DFS 문제를 많이 풀어보지 못해서 이전에 풀었던 문제를 한 번 정리하고 파이썬 언어로 다시 풀어볼 생각이다.