[SQL/오답] Recursive CTE의 두 방향성: 조직 계층 및 예산 합산(LeetCode3482 Hard)

1. Problem

조직 구조 데이터에서 각 직원의 계층 레벨, 관리하는 팀 규모(직/간접 부하 포함), 그리고 본인과 하위 직원을 포함한 전체 급여 예산을 계산해야 한다. 단순히 직속 부하만 찾는 것이 아니라, 최하위 노드부터 최상위 관리자까지 이어지는 모든 경로를 파악하여 누적 집계를 수행하는 것이 이 문제의 핵심 난제이다.

2. Solution

레벨 확정을 위한 Top-Down(하향식) 탐색과 예산 집계를 위한 Bottom-Up(상향식) 탐색을 분리하여 설계한 뒤, 마지막에 결합하는 방식을 채택한다.

3. Takeaway (핵심 통계 논리)

단순한 계층 조회를 넘어 비즈니스 지표(예산)를 산출하기 위해 다음의 기술적 원리를 정립한다.

• 재귀의 방향성 분리: Hierarchy는 위에서 아래로 내려가며 '레벨'을 확정 짓는 용도인 반면, PathToRoot는 아래에서 위로 거슬러 올라가며 '이 사원이 누구의 예산에 속하는지' 매핑하는 용도이다. 두 쿼리는 목표가 정반대이므로 각각 수행 후 조인하는 것이 가장 정확하다.
• 데이터의 팽창을 활용한 집계: PathToRoot 단계를 거치면 직원은 10명이지만 매핑 데이터는 28행으로 늘어난다. 이 팽창된 데이터를 상사 ID(mgr_id) 기준으로 그룹화함으로써 간접 부하까지 포함된 team_size와 budget을 한 번에 계산할 수 있다.
• 자기 참조(Anchor)의 중요성: 모든 사원은 '자기 자신'이라는 조직의 팀장이자 팀원이라는 점을 Anchor 쿼리에서 정의해야 누락 없는 예산 합산이 가능하다.

https://leetcode.com/problems/analyze-organization-hierarchy/description/

Analyze Organization Hierarchy - LeetCode

문제

Table: Employees

+----------------+---------+
| Column Name    | Type    | 
+----------------+---------+
| employee_id    | int     |
| employee_name  | varchar |
| manager_id     | int     |
| salary         | int     |
| department     | varchar |
+----------------+----------+
employee_id is the unique key for this table.
Each row contains information about an employee, including their ID, name, their manager''s ID, salary, and department.
manager_id is null for the top-level manager (CEO).
Write a solution to analyze the organizational hierarchy and answer the following:

Hierarchy Levels: For each employee, determine their level in the organization (CEO is level 1, employees reporting directly to the CEO are level 2, and so on).
Team Size: For each employee who is a manager, count the total number of employees under them (direct and indirect reports).
Salary Budget: For each manager, calculate the total salary budget they control (sum of salaries of all employees under them, including indirect reports, plus their own salary).
Return the result table ordered by the result ordered by level in ascending order, then by budget in descending order, and finally by employee_name in ascending order.

The result format is in the following example.

 

Example:

Input:

Employees table:

+-------------+---------------+------------+--------+-------------+
| employee_id | employee_name | manager_id | salary | department  |
+-------------+---------------+------------+--------+-------------+
| 1           | Alice         | null       | 12000  | Executive   |
| 2           | Bob           | 1          | 10000  | Sales       |
| 3           | Charlie       | 1          | 10000  | Engineering |
| 4           | David         | 2          | 7500   | Sales       |
| 5           | Eva           | 2          | 7500   | Sales       |
| 6           | Frank         | 3          | 9000   | Engineering |
| 7           | Grace         | 3          | 8500   | Engineering |
| 8           | Hank          | 4          | 6000   | Sales       |
| 9           | Ivy           | 6          | 7000   | Engineering |
| 10          | Judy          | 6          | 7000   | Engineering |
+-------------+---------------+------------+--------+-------------+
Output:

+-------------+---------------+-------+-----------+--------+
| employee_id | employee_name | level | team_size | budget |
+-------------+---------------+-------+-----------+--------+
| 1           | Alice         | 1     | 9         | 84500  |
| 3           | Charlie       | 2     | 4         | 41500  |
| 2           | Bob           | 2     | 3         | 31000  |
| 6           | Frank         | 3     | 2         | 23000  |
| 4           | David         | 3     | 1         | 13500  |
| 7           | Grace         | 3     | 0         | 8500   |
| 5           | Eva           | 3     | 0         | 7500   |
| 9           | Ivy           | 4     | 0         | 7000   |
| 10          | Judy          | 4     | 0         | 7000   |
| 8           | Hank          | 4     | 0         | 6000   |
+-------------+---------------+-------+-----------+--------+
Explanation:

Organization Structure:
Alice (ID: 1) is the CEO (level 1) with no manager
Bob (ID: 2) and Charlie (ID: 3) report directly to Alice (level 2)
David (ID: 4), Eva (ID: 5) report to Bob, while Frank (ID: 6) and Grace (ID: 7) report to Charlie (level 3)
Hank (ID: 8) reports to David, and Ivy (ID: 9) and Judy (ID: 10) report to Frank (level 4)
Level Calculation:
The CEO (Alice) is at level 1
Each subsequent level of management adds 1 to the level
Team Size Calculation:
Alice has 9 employees under her (the entire company except herself)
Bob has 3 employees (David, Eva, and Hank)
Charlie has 4 employees (Frank, Grace, Ivy, and Judy)
David has 1 employee (Hank)
Frank has 2 employees (Ivy and Judy)
Eva, Grace, Hank, Ivy, and Judy have no direct reports (team_size = 0)
Budget Calculation:
Alice''s budget: Her salary (12000) + all employees'' salaries (72500) = 84500
Charlie''s budget: His salary (10000) + Frank''s budget (23000) + Grace''s salary (8500) = 41500
Bob''s budget: His salary (10000) + David''s budget (13500) + Eva''s salary (7500) = 31000
Frank''s budget: His salary (9000) + Ivy''s salary (7000) + Judy''s salary (7000) = 23000
David''s budget: His salary (7500) + Hank''s salary (6000) = 13500
Employees with no direct reports have budgets equal to their own salary
Note:

The result is ordered first by level in ascending order
Within the same level, employees are ordered by budget in descending order then by name in ascending order

 

왜 Hierarchy와 PathToRoot를 따로 나누었나?

"하나로 합칠 수 없나?"라고 생각하실 수 있지만 두 쿼리는 목표가 정반대이다.

1. Hierarchy (Top-Down): CEO(1) → 부장(2) → 대리(3) 순으로 내려가며 **'레벨'**을 확정 짓는 용도.
2. PathToRoot (Bottom-Up): 말단(사원) → 대리 → 부장 → CEO 순으로 거슬러 올라가며 '이 사원이 누구의 예산에 속하는지' 맵핑하는 용도.

서로 방향이 다르기 때문에 각각 재귀를 돌려 정보를 만든 뒤, 마지막에 JOIN으로 합치는 것이 가장 논리적이고 정확하다.

 

정답 쿼리 

WITH RECURSIVE Hierarchy AS (
    -- 1. 기초 계층 및 레벨 계산 (Top-down)
    SELECT 
        employee_id, 
        employee_name, 
        manager_id, 
        salary, 
        1 AS level
    FROM Employees
    WHERE manager_id IS NULL  -- CEO부터 시작

    UNION ALL

    SELECT 
        e.employee_id, 
        e.employee_name, 
        e.manager_id, 
        e.salary, 
        h.level + 1
    FROM Employees e
    JOIN Hierarchy h ON e.manager_id = h.employee_id
),
PathToRoot AS (
    -- 2. 모든 사원으로부터 상위 관리자로 거슬러 올라가는 관계 매핑 (Bottom-up 준비)
    SELECT 
        employee_id AS sub_id, 
        employee_id AS mgr_id, 
        salary
    FROM Employees

    UNION ALL

    SELECT 
        p.sub_id, 
        e.manager_id, 
        p.salary
    FROM PathToRoot p
    JOIN Employees e ON p.mgr_id = e.employee_id
    WHERE e.manager_id IS NULL IS FALSE -- 상위 관리자가 존재할 때까지 반복
)
-- 3. 두 정보를 결합하여 결과 도출
SELECT 
    h.employee_id,
    h.employee_name,
    h.level,
    -- 본인을 제외한 하위 인원 수 계산
    COALESCE(sub.team_size, 0) AS team_size,
    -- 본인 급여를 포함한 전체 하위 급여 합계 계산
    COALESCE(sub.budget, h.salary) AS budget
FROM Hierarchy h
LEFT JOIN (
    SELECT 
        mgr_id, 
        COUNT(*) - 1 AS team_size, 
        SUM(salary) AS budget
    FROM PathToRoot
    GROUP BY mgr_id
) sub ON h.employee_id = sub.mgr_id
ORDER BY h.level ASC, budget DESC, h.employee_name ASC;

쿼리 핵심 포인트 분석

1. Hierarchy (레벨 계산)

• CEO를 level 1로 설정하고 재귀적으로 자식 노드를 찾아가며 level + 1을 수행합니다. 이는 출력 결과의 level 컬럼을 위한 전형적인 계층 탐색입니다.

2. PathToRoot (팀 사이즈 및 예산 계산)

• 이 부분이 가장 중요합니다. 단순히 manager_id만 봐서는 직계 부하만 알 수 있습니다.
• 모든 사원(sub_id)이 자신의 모든 상사(mgr_id)를 찾아가도록 재귀를 돌립니다. 이렇게 하면 특정 상사(mgr_id) 밑에 누가(sub_id) 있는지 전수 조사가 가능합니다.
• COUNT(*) - 1: 그룹화했을 때 자기 자신도 포함되므로 1을 빼서 team_size를 구합니다.
• SUM(salary): 상사 본인과 모든 하위 직원의 급여를 합산하여 budget을 구합니다.

(1) Anchor: 모든 사원은 자기 자신의 예산에 포함된다

SELECT 
    employee_id AS sub_id,  -- 실제 돈을 받는 사원 (부하)
    employee_id AS mgr_id,  -- 그 돈을 관리하는 상사 (현재는 본인)
    salary                  -- 금액
FROM Employees

• 의미: 모든 사원은 '자기 자신'이라는 조직의 팀장이자 팀원입니다.
• 결과: (Alice, Alice, 12000), (Bob, Bob, 10000) 같은 데이터가 생성됩니다.

(2) Recursive: 내 상사의 상사, 그 상사의 상사까지 끝까지 추적

SELECT 
    p.sub_id,       -- 돈을 받는 사원은 그대로 유지
    e.manager_id,   -- mgr_id를 '내 상사의 manager_id'로 한 단계 올림
    p.salary        -- 금액도 그대로 유지
FROM PathToRoot p
JOIN Employees e ON p.mgr_id = e.employee_id -- 내 상사의 정보를 가져옴
WHERE e.manager_id IS NOT NULL -- 상사가 더 있을 때까지만 반복

• 작동 원리:
  1. p.mgr_id가 'Bob'이라면, Employees 테이블에서 'Bob'의 상사인 'Alice'를 찾습니다.
  2. 새로운 행 (Bob, Alice, 10000)이 생성됩니다.
  3. 이제 'Alice'가 mgr_id가 되어 다시 재귀를 돕니다. 하지만 Alice는 상사가 없으므로 종료됩니다.

(3) PathToRoot  전체 재귀 테이블 (Full Trace)

이 표는 PathToRoot CTE가 실행된 후 최종적으로 쌓이는 결과값입니다.

sub_id는 돈을 받는 당사자, mgr_id는 그 돈이 포함될 상사 장부의 주인입니다.

단계	sub_id (급여 대상자)	mgr_id (상속될 상사)	salary	데이터 출처 및 관계
Anchor	1 (Alice)	1	12,000	본인 (CEO)
Anchor	2 (Bob)	2	10,000	본인
1차 루프	2 (Bob)	1	10,000	Alice의 직속 부하
Anchor	3 (Charlie)	3	10,000	본인
1차 루프	3 (Charlie)	1	10,000	Alice의 직속 부하
Anchor	4 (David)	4	7,500	본인
1차 루프	4 (David)	2	7,500	Bob의 직속 부하
2차 루프	4 (David)	1	7,500	Alice의 하위 부하 (Bob 경유)
Anchor	5 (Eva)	5	7,500	본인
1차 루프	5 (Eva)	2	7,500	Bob의 직속 부하
2차 루프	5 (Eva)	1	7,500	Alice의 하위 부하 (Bob 경유)
Anchor	6 (Frank)	6	9,000	본인
1차 루프	6 (Frank)	3	9,000	Charlie의 직속 부하
2차 루프	6 (Frank)	1	9,000	Alice의 하위 부하 (Charlie 경유)
Anchor	7 (Grace)	7	8,500	본인
1차 루프	7 (Grace)	3	8,500	Charlie의 직속 부하
2차 루프	7 (Grace)	1	8,500	Alice의 하위 부하 (Charlie 경유)
Anchor	8 (Hank)	8	6,000	본인
1차 루프	8 (Hank)	4	6,000	David의 직속 부하
2차 루프	8 (Hank)	2	6,000	Bob의 하위 부하 (David 경유)
3차 루프	8 (Hank)	1	6,000	Alice의 하위 부하 (David, Bob 경유)
Anchor	9 (Ivy)	9	7,000	본인
1차 루프	9 (Ivy)	6	7,000	Frank의 직속 부하
2차 루프	9 (Ivy)	3	7,000	Charlie의 하위 부하 (Frank 경유)
3차 루프	9 (Ivy)	1	7,000	Alice의 하위 부하 (Frank, Charlie 경유)
Anchor	10 (Judy)	10	7,000	본인
1차 루프	10 (Judy)	6	7,000	Frank의 직속 부하
2차 루프	10 (Judy)	3	7,000	Charlie의 하위 부하 (Frank 경유)
3차 루프	10 (Judy)	1	7,000	Alice의 하위 부하 (Frank, Charlie 경유)

1. 데이터의 팽창: 보시는 것처럼 원래 직원은 10명이지만, 계층을 타고 올라가며 생성된 매핑 데이터는 총 28행입니다.
2. Budget의 비밀: mgr_id 컬럼을 기준으로 같은 숫자를 찾아보세요. 예를 들어 mgr_id = 6 (Frank)인 행은 총 3개(sub_id 6, 9, 10)입니다. 이들의 salary 합(9,000 + 7,000 + 7,000)이 Frank의 **Budget(23,000)**이 됩니다.
3. Team Size의 비밀: 위와 동일하게 mgr_id = 6인 행의 개수를 세면 3개입니다. 여기서 본인(Frank)을 제외하면 Team Size 2가 나옵니다.

3. Join 및 정렬

• 계산된 레벨 정보(Hierarchy)와 집계 정보(sub)를 employee_id 기준으로 결합합니다.
• 문제에서 요구한 대로 Level(오름차순) → Budget(내림차순) → Name(오름차순) 순으로 정렬합니다.