[프로그래머스 Level.5] 멸종위기의 대장균 찾기

문제

대장균들은 일정 주기로 분화하며, 분화를 시작한 개체를 부모 개체, 분화가 되어 나온 개체를 자식 개체라고 합니다. 다음은 실험실에서 배양한 대장균들의 정보를 담은 ECOLI_DATA 테이블입니다. ECOLI_DATA 테이블의 구조는 다음과 같으며, ID, PARENT_ID, SIZE_OF_COLONY, DIFFERENTIATION_DATE, GENOTYPE는 각각 대장균 개체의 ID, 부모 개체의 ID, 개체의 크기, 분화되어 나온 날짜, 개체의 형질을 나타냅니다.

Column name	Type	Nullable
ID	INTEGER	FALSE
PARENT_ID	INTEGER	TRUE
SIZE_OF_COLONY	INTEGER	FALSE
DIFFERENTIATION_DATE	DATE	FALSE
GENOTYPE	INTEGER	FALSE

최초의 대장균 개체의 PARENT_ID는 NULL 값입니다.

문제

각 세대별 자식이 없는 개체의 수(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

각 세대별 대장균의 ID는 다음과 같습니다.

• 1 세대: ID 1, ID 2
• 2 세대: ID 3, ID 4, ID 5
• 3 세대: ID 6, ID 7
• 4 세대: ID 8

이 때 각 세대별 자식이 없는 대장균의 ID는 다음과 같습니다.

• 1 세대: ID 1
• 2 세대: ID 3, ID 5
• 3 세대: ID 7
• 4 세대: ID 8

따라서 결과를 세대에 대해 오름차순 정렬하면 다음과 같습니다.

COUNT	GENERATION
1	1
2	2
1	3
1	4

---

소스코드

WITH RECURSIVE GENERATIONS AS (
    SELECT
        ID,
        PARENT_ID,
        1 AS GENERATION
    FROM
        ECOLI_DATA
    WHERE
        PARENT_ID IS NULL
    
    UNION ALL
    
    SELECT
        E.ID,
        E.PARENT_ID,
        G.GENERATION + 1 AS GENERATION
    FROM
        ECOLI_DATA AS E
    JOIN
        GENERATIONS AS G
    ON
        E.PARENT_ID = G.ID

)

SELECT COUNT(*) AS COUNT, GENERATION
FROM GENERATIONS AS G1
WHERE NOT EXISTS (
    SELECT 1
    FROM GENERATIONS G2
    WHERE G2.PARENT_ID = G1.ID
)
GROUP BY GENERATION
ORDER BY GENERATION;

---

쿼리 설명

WHERE NOT EXISTS (
    SELECT 1
    FROM GENERATIONS G2
    WHERE G2.PARENT_ID = G1.ID
)

1. SELECT 1

• EXISTS는 서브쿼리에서 실제로 어떤 데이터를 반환하는지는 중요하지 않기 때문에, SELECT 1처럼 단순한 값을 반환하도록 쓸 수 있습니다.
• EXISTS의 역할은 해당 조건을 만족하는 행이 있는지 여부만 판단하는 것이기 때문에, 1을 반환해도 상관없습니다.

2. FROM GENERATIONS G2

• EXISTS 절 안에서 쿼리를 다시 작성하고 있습니다. 여기서 GENERATIONS 테이블의 또 다른 인스턴스를 G2라는 별칭으로 정의합니다. 이 부분에서 GENERATIONS 테이블을 두 번 사용하게 되는 것이죠.
  • G1: 외부 쿼리에서 사용되는 GENERATIONS 테이블의 별칭.
  • G2: 서브쿼리 안에서 사용되는 GENERATIONS 테이블의 별칭.

3. WHERE G2.PARENT_ID = G1.ID

• 이 부분은 G1 테이블의 ID 값이 G2 테이블의 PARENT_ID에 존재하는지를 확인하는 조건입니다.
• 즉, G1.ID가 G2의 자식 노드인지 확인합니다.

4. NOT EXISTS

• NOT EXISTS는 위에서 조건을 만족하는 행이 존재하지 않을 때 참이 됩니다.
• 즉, G1.ID가 어떤 행의 부모가 되지 않는 경우, 즉 자식이 없는 경우를 의미합니다. 자식이 없는 노드를 리프 노드라고 부릅니다.

전체적인 작동 원리

• 이 조건은 자식 노드가 없는 노드들만 선택하는 것입니다. G1의 ID 값이 다른 행의 PARENT_ID로 존재하지 않는다면, 이는 리프 노드이기 때문에 WHERE NOT EXISTS 조건을 만족하게 됩니다.
• 쉽게 말해, G1.ID가 다른 행의 PARENT_ID로 존재하지 않는다는 것은, G1.id가 자식을 가지고 있지 않다는 뜻입니다.