멸종위기의 대장균 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/301651

프로그래머스

문제

각 세대별 자식이 없는 개체의 수(COUNT)와 세대(GENERATION)를 출력하는 SQL문을 작성해주세요. 이때 결과는 세대에 대해 오름차순 정렬해주세요. 단, 모든 세대에는 자식이 없는 개체가 적어도 1개체는 존재합니다.

 

ECOLI_DATA 테이블

ID	PARENT_ID	SIZE_OF_COLONY	DIFFERENTIATION_DATE	GENOTYPE
1	NULL	10	2019-01-01	5
2	NULL	2	2019-01-01	3
3	2	100	2020-01-01	4
4	2	16	2020-01-01	4
5	2	17	2020-01-01	6
6	4	101	2021-01-01	22
7	4	101	2022-01-01	23
8	6	1	2022-01-01	27

 

WITH RECURSIVE TEMP AS(
    SELECT ID, PARENT_ID, 1 AS GENERATION
    
    FROM ECOLI_DATA 
    
    WHERE PARENT_ID IS NULL
    
    UNION ALL
    
    SELECT 
            ED2.ID, ED2.parent_id, GENERATION + 1
    
    FROM   ECOLI_DATA ED2
    
    JOIN  TEMP ON ED2.PARENT_ID = TEMP.ID
    
)
SELECT
        COUNT(*) AS COUNT, GENERATION
FROM
        TEMP T1
WHERE
        ID NOT IN
        (
            SELECT
                    PARENT_ID
            FROM
                    TEMP
            WHERE
                    PARENT_ID IS NOT NULL
        )
GROUP BY GENERATION
ORDER BY
        T1.GENERATION

명성 답게 어려운 문제였다. 세대를 구할 때 재귀쿼리를 써야 하는건 생각 났지만 어떻게 써야하는지 몰랐고 자식이 없는 ID는 어떻게 찾을지 감 조차 오지 않았다. 
결국 클로드 도움을 받았고 답지를 참조했다. 이 세상 모든 문제가 그렇듯 보고 나면 쉽다. 우선 재귀쿼리부터 다시 설명한다.

WITH RECURSIVE cte_name AS (
    -- 기본 케이스(Base case): 재귀의 시작점
    SELECT columns FROM table WHERE condition
    
    UNION ALL  -- 또는 UNION
    
    -- 재귀 케이스(Recursive case): 이전 결과를 기반으로 다음 단계 계산
    SELECT columns 
    FROM cte_name JOIN table
    ON join_condition
    WHERE recursive_condition
)
SELECT * FROM cte_name;

재귀 쿼리에서 UNION ALL위에 있는 쿼리는 단 한번만 작동한다. 이를 기본 케이스라고 한다. UNION ALL 아래에 있는 재귀 케이스는 조건문이라 할 수있다. 내가 쓴 정답에서 재귀쿼리 부분을 보자

    SELECT ID, PARENT_ID, 1 AS GENERATION
    
    FROM ECOLI_DATA 
    
    WHERE PARENT_ID IS NULL
    
    UNION ALL
    
    SELECT 
            ED2.ID, ED2.parent_id, GENERATION + 1
    
    FROM   ECOLI_DATA ED2
    
    JOIN  TEMP ON ED2.PARENT_ID = TEMP.ID

우선 기본쿼리를 실행한다. 

아래는 실행결과

ID	PARENT_ID	GENERATION
1	null	1
2	null	1

그다음 재귀 쿼리를 실행한다. 이 부분은 재귀쿼리와 SELF JOIN형태를 합친 것과 비슷하다. 

재귀 쿼리를 처음 실생하면 ED2의 부모 ID와 기본쿼리의 ID가 같은 행을 찾는다. 그러니 테이블 중에서 부모ID가 1 혹은 2 세대인 것을 찾는다. 그런 ID는 3, 4, 5다. 이전 세대가 1세대 였으니 GENERATION 을 1 더해준다. 한번더 결과를 돌리면 

ID	PARENT_ID	GENERATION
3	2	2
4	2	2
5	2	2

이렇게 나온다. 감을 잡기 위해서 한번만 더 실행 해 보자.

재귀 쿼리를 한번 더 실행하면 ED2의 부모ID와 이전 결과물의 ID가 같은 것을 찾으면

부모ID를 4로 같는 6과 7이 ID다. 세대도 1 늘리면

ID	PARENT_ID	GENERATION
6	4	3
7	4	3

이렇게 끝 까지 다 돌려주면 

ID	PARENT_ID	GENERATION
1	null	1
2	null	1
3	2	2
4	2	2
5	2	2
6	4	3
7	4	3
8	6	4

이런 결과가 나온다. 리마인드. 우리가 찾아야 할 놈들은 자식이 없는 ID다. 어떻게 찾을까? PARENT_ID를 자세히 보자. PARENT_ID 에 있는 ID는 모두 자식이 있다는 뜻이다. 그래서 서브쿼리와 NOT IN을 쓰면 자식이 없는 ID를 찾을 수  있다. 이를 이용해서 자식이 없는 ID를 찾는다. 

 

SELECT
        COUNT(*) AS COUNT, GENERATION
FROM
        TEMP T1
WHERE
        ID NOT IN
        (
            SELECT
                    PARENT_ID
            FROM
                    TEMP
            WHERE
                    PARENT_ID IS NOT NULL
        )
GROUP BY GENERATION
ORDER BY
        T1.GENERATION

서브쿼리를 주목하자. 부모 아이디를선택하고 부모 아이디가 NULL인 값을 선택한다. 결국 부모 아이디를 선택하는 건대 이 말은 부모 = 자식이 있는다는 뜻이다. NOT IN을 써서 자식이 없는 ID를(부모가 아닌) 선택한다.

그러면 세대별로 묶어서 개수를 세면

COUNT	GENERATION
1	1
2	2
1	3
1	4

 

최종 완성된 결과물이다.