문제 소개
직원 정보를 저장하는 데이터 구조가 있다고 가정해 보겠습니다. 각 직원은 고유 ID(id), 중요도 값(importance), 그리고 직속 부하 직원들의 ID 목록으로 구성됩니다.
예를 들어, 직원 1이 직원 2의 상사이고, 직원 2가 직원 3의 상사라고 하겠습니다. 세 직원의 중요도가 각각 15, 10, 5라면 데이터 구조는 다음과 같이 표현됩니다.
- 직원 1 → [1, 15, [2]]
- 직원 2 → [2, 10, [3]]
- 직원 3 → [3, 5, []]
즉, 회사의 전체 직원 정보와 하나의 직원 ID가 주어졌을 때, 해당 직원 본인과 그 아래 모든 부하 직원(간접 부하 포함)의 중요도 총합을 계산하는 것이 이 문제의 목표입니다.
예제 입력 및 출력
입력이 [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1이라면 출력은 11이 됩니다. 그 이유는 다음과 같습니다.
- 직원 1(Emp1)의 중요도는 5입니다.
- 직원 1의 직속 부하는 직원 2(Emp2)와 직원 3(Emp3)이며, 두 사람의 중요도는 각각 3입니다.
- 따라서 직원 1의 총 중요도는 5 + 3 + 3 = 11입니다.
해결 접근 방법
이 문제는 해시 맵(hash map)과 큐(queue)를 활용한 그래프 순회 방식으로 해결할 수 있습니다. 단계별 풀이 과정은 다음과 같습니다.
- weight := 새로운 맵 생성, leader := 새로운 맵 생성
- employees의 각 요소 e에 대해 다음을 수행
- weight[e[0]] := e[1] (ID별 중요도 저장)
- leader[e[0]] := e[2] (ID별 부하 목록 저장)
- res := 0으로 초기화한 뒤 res에 weight[id]를 더함
- queue := leader[id] (대상 직원의 직속 부하 목록으로 큐 초기화)
- queue가 비어 있지 않은 동안 반복
- new_queue := 새로운 리스트 생성
- node := queue에서 마지막 요소를 꺼냄
- res := res + weight[node]
- leader[node]가 비어 있지 않으면 new_queue에 leader[node]를 추가
- queue := queue + new_queue
- res를 반환
아래 예제 코드를 통해 더 자세히 살펴보겠습니다.
구현 코드
class Solution(object):
def getImportance(self, employees, id):
weight = {}
leader = {}
for e in employees:
weight[e[0]] = e[1]
leader[e[0]] = e[2]
res = 0
res += weight[id]
queue = leader[id]
while queue:
new_queue = []
node = queue.pop()
res += weight[node]
if leader[node]:
new_queue += leader[node]
queue += new_queue
return res
ob = Solution()
print(ob.getImportance([[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1))입력
[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
출력
11
마무리 정리
이 풀이는 먼저 각 직원의 중요도와 부하 목록을 딕셔너리에 저장해 O(1) 시간에 조회할 수 있도록 준비한 뒤, 큐를 이용해 조직도를 따라 내려가며 중요도를 누적하는 방식입니다. 직원 수를 N이라 할 때 시간 복잡도와 공간 복잡도 모두 O(N)입니다. 또한 재귀 호출 대신 반복문으로 구현했기 때문에 조직 계층이 아무리 깊어져도 스택 오버플로우 없이 안정적으로 동작한다는 장점이 있습니다.