690. Employee Importance

출처

[문제 설명]

직원들의 리스트와 직원 아이디가 주어졌을 때,
주어진 아이디와 일치하는 직원의 중요도와 그 직원의 모든 부하직원들의 중요도의 총합을 구하시오.
예제에서는 주어진 id가 1이고, 부하 직원이 두명 밖에 없으므로 이 셋의 합인 5+3+3인 11이 됩니다.

[처음 생각한 접근 방법]
보자마자 생각 난 건 일단 리스트로 직원이 주어졌으니 리스트(employees)에서 아이디(id)와 일치하는 employee를 찾아서 뽑는 것입니다.
그 후에 해당 employee를 Queue에 넣고 bfs로 모든 요소를 검색한 후, 각 요소들의 중요도(importance)를 총합을 구합니다.

이렇게 풀려고 했는데 막상 보니까 employee의 subordinates가 아이디(id)를 담은 리스트였습니다.
저는 당연히 List subordinates(원소가 직원인 리스트)인줄 알았는데
List subordinates(원소가 직원의 아이디인 리스트)였습니다.

따라서 아이디로 직원을 검색하는 절차가 필요하게 됐습니다.
매번 직원 리스트에서 아이디를 검색하는 건 좋아보이지 않습니다.
그래서 맨 처음, Map<직원의아이디,직원객체> map을 만들도록 한 후, id와 일치하는 employee를 찾는 for문에서 맵에 다 넣어줬습니다.
이렇게 하면 아이디(id)를 이용해서 map에서 get(id)를 하여 직원을 가져옵니다.

[내가 쓴 코드]

class Solution {
    public int getImportance(List<Employee> employees, int id) {
          //bfs 구현을 위한 Queue 생성.
        Queue<Employee> q = new LinkedList<>();
          //key는 직원의 아이디 value는 직원인 map을 구현.
          //아이디로 직원을 구하기 위함.
        Map<Integer, Employee> map = new HashMap<>();

        for (Employee emp : employees) {
              //찾는 아이디가 일치하면, Queue의 root로 등록.
            if (emp.id == id) {
                q.offer(emp);
                  //root를 다시 찾을 일은 없으므로 
                  //다음 반복문으로 넘어감.
                  continue;
            }

              //key를 아이디, value를 직원으로 넣어줌.
            map.put(emp.id, emp);
        }

          //중요도(importance)의 총합에 쓰일 변수 초기화.
        int total = 0;

          //bfs구현
        while (!q.isEmpty()) {
            Employee emp = q.poll();
              //나온 직원의 중요도(importance)를 더해줌.
            total += emp.importance;

              //Iterator로 리스트의 각각 요소를 가져옴.
            Iterator<Integer> it = emp.subordinates.iterator();
              //리스트만큼 반복.
            while (it.hasNext()) {
                  //id로 맵에서 직원을 구해와서
                  //queue에 넣어줌.
                q.offer(map.get(it.next()));
            }
        }

        return total;
    }
}

리트코드 최다 추천 답안

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        int total = 0;
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee employee : employees) {
            map.put(employee.id, employee);
        }
        Queue<Employee> queue = new LinkedList<>();
        queue.offer(map.get(id));
        while (!queue.isEmpty()) {
            Employee current = queue.poll();
            total += current.importance;
            for (int subordinate : current.subordinates) {
                queue.offer(map.get(subordinate));
            }
        }
        return total;
    }
}

사실상 똑같은 순서인데 이 사람은 그냥 다 넣어준 다음에, 매개변수 id로 root를 따로 넣어줬음.
if문을 덜 태워서 더 좋은 거 같습니다.
제 코드의 경우 if를 employees를 돌면서 계속 체크하는데 그럴 필요가 없어보입니다.