[알고리즘문제] 릿코드 Employee Importance

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

Employee Importance - LeetCode

 

사원의 중요도를 표현한 객체와 중요도를 계산할 id값을 입력 받는다.

ex) 중요도 : [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id : 1

id가 1번인 사원의 중요도를 출력해야 된다.

1번 노드의 하위 노드는 2, 3이고 1번의 중요도가 5, 2번/3번의 중요도가 3이므로 모두 더해서 출력시켜야 한다.

답은 11이 될것이다.

 

leetcode에서 example을 저렇게 줘서 배열인줄 알았다.

하지만 객체였고 배열기준으로 코드를 작성해서 시간 관계상 input객체를 배열로 빠르게 바꾸어 주는 로직을 추가했다.

(처음부터 객체인줄 알았다면 배열로 바꿀 필요가 없었지)

 

javascript  풀이

time complexity = O(n)

space complexity = O(n) 일껄 아마도...

var GetImportance = function(employees, id) {
    let hap = 0;
    let arr = [];
    for(let i = 0; i < employees.length; i++){
        let tmp = [];
        tmp.push(employees[i].id);
        tmp.push(employees[i].importance);
        tmp.push(employees[i].subordinates);
        arr.push(tmp);
    }
    return dfs(arr, id, hap);
};

var dfs = function(employees, id, hap){
    let position = 0;
    for(let i = 0; i < employees.length; i++){
        if(employees[i][0] === id){
            position = i;
            break;
        }
    }
    if(!employees[position][2]){
        return employees[position][1];
    }
    hap = employees[position][1];
    for(let i = 0; i < employees[position][2].length; i++){
        hap += dfs(employees, employees[position][2][i], hap);
    }
    return hap;
}