[코딩테스트] sumOfSubOrdinates - DFS (JavaScript)

문제

There is a company in which the relationships of employees are hierarchical.

For example, If there is a subordinate B whose boss is A, then B's subordinate C is also a subordinate of A.

A HR staff wants to know the total number of subordinates for a specific employee in the company.

Complete a function that returns the sum of subordinates of employee from hierarchcy.Each employee cannot be duplicated.

매개변수

• hierarchy :Object type with employees with subordinates
• employee : String type

아웃풋

• Number Type :  the total number of subordinates including employee should be returned.

예시

const hierarchy = {
  A: ["B", "C"],
  B: ["D", "E"],
  C: ["F"],
  D: ["G", "H", "I"],
  E: ["J", "K"],
  F: ["L", "M"],
  G: ["N", "O", "P"],
  H: ["Q", "R"],
  J: ["S"],
  L: ["T", "U", "V"],
};
const employee = 'B';

const output = sumOfSubOrdinates(hierarchy, employee);
console.log(output); // 14

 

솔루션1 (DFS)

결과를 담을 변수 result 선언하기

dfs를 통해 부하직원이 있는 경우 result에 1을 더해주기

 

function sumOfSubOrdinates(hierarchy, employee) {

  // 결과를 담을 변수를 선언하고 1을 할당 (employee 본인을 포함해야 하기 때문)
  let result = 1;

  // dfs 함수 제작 (전달인자 str에는 직원에 해당하는 문자열 입력)
  function dfs (str) {  
    // subordinate가 없는 경우 바로 리턴
    if (!hierarchy[str]) return;

    // subordinate가 있는 경우 배열을 순회하기
    for (let ele of hierarchy[str]) {
      result += 1;
      dfs(ele)
    }
  }

  dfs(employee);
  
  return result;
}

 

 

솔루션2 (DFS)

선언된 result 배열에 부하직원을 push하여, 배열 엘리먼트 개수 구하기

 

function sumOfSubOrdinates(hierarchy, employee) {
 
 // start로 특정직원을 넣어주기 
 let result = [employee];
 
   //호출할 재귀 aux
  const aux = function (hierarchy, node) {
    //base case 더 이상 부하직원이 없을 때,
    if (hierarchy[node] === undefined) return;
	
    //recursive case 탐색할 부하직원이 있을 때,
    else {
      const needChecked = hierarchy[node];
      for (let i = 0; i < needChecked.length; i++) {
        //확인된 부하직원은 result에 계속 넣어준다.
        result.push(needChecked[i]);
        aux(hierarchy, needChecked[i]);
      }
    }
  };
  
  aux(hierarchy, employee);
  return result.length;
}