[SQL] 멸종위기의 대장균 찾기

시용언어 : MYSQL

LEVEL : 5

문제 : 멸종위기의 대장균 찾기

프로그래머스

문제풀이

WITH RECURSIVE generations AS (
    SELECT id,
        COALESCE(parent_id, 0) AS 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 E
    JOIN generations G
    ON E.parent_id = G.id
)
SELECT
    COUNT(*) AS count,
    G.generation AS generation
FROM generations G
LEFT JOIN ECOLI_DATA E
ON G.id = E.parent_id
WHERE E.id IS NULL
GROUP BY G.generation
ORDER BY G.generation;

- 자식이 없는 개체의 수를 각 세대별로 계산하기 위해서는 ECOLI_DATA 테이블의 정보를 세대별로 그룹화 한 뒤, 각 그룹에서 자식이 없는 개체의 수를 세어야 한다.

- 또한 각 개체의 세대는 부모 개체의 세대보다 1만큼 높아야한다.(초기 개체의 세대는 1)

 

<각 개체의 세대를 계산하는 방법>

- 각 개체가 어느 세대에 속하는지를 계산하기 위해서는 재귀적 조인을 사용해서 각 개체의 부모 자식 관계를 따라가며 세대를 계산해야한다. (WITH RECURSIVE문 사용)

참고 - Inpa DeV

 

1. 조건 설정

- SELECT 절에서는 id, COALESCE(parent_id, 0) AS parent_id, 1 AS generation을 선택한다. (초기 개체들의 세대는 1로 설정)

- WHERE 절에서는 parent_id IS NULL 조건을 사용하여 부모 개체가 없는(즉, parent_id가 NULL인) 초기 개체들을 선택한다.

- 초기 개체들은 세대의 시작점이므로 generation을 1로 설정

 

2. 재귀 단계

- UNION ALL을 사용하여 초기 조건과 재귀적으로 조인된 결과를 확장

- JOIN을 사용하여 ECOLI_DATA과 generations CTE를 조인 (자식 개체의 parent_id와 부모 개체의 id)

    *CTE( Common Table Expressions):  복잡한 SQL 쿼리를 단순화하는 데 사용되는 일시적인 결과 집합으로, 쿼리 실행                                                                  시 한번 정의된다.

- 조인된 결과를 통해 부모 객체의 generation에 1을 더해 자식 객체의 generation을 계산

 

3. 종료

- 더 이상 새로운 개체가 없는 경우 재귀 조인이 종료

 

<자식이 없는 개체 찾는 방법>

- 자식이 없는 개체를 찾는 방법은 LEFT JOIN을 통해 식별할 수 있다.

 

1. 자식이 없는 개체 식별

- LEFT JOIN을 사용하여 ECOLI_DATA 테이블을 조인(각 개체의 ID가 다른 개체의 PARENT_ID와 일치하는지 확인)

- LEFT JOIN을 통해 부모 개체의 ID에 상응하는 자식 개체의 ID가 존재하지 않는경우 NULL로 표시되는데, 이는 자식이 없는 개체를 의미한다.

 

2. 새대별 그룹화 / 계산

- 앞에서 자식이 없는 개체를 식별한 뒤 GROUP BY를 통해 세대별로 그룹화

- 각 그룹에서 COUNT(*)를 사용해 자식이 없는 개체의 수를 계산

 

3. 최종 정렬

- GROUP BY를 사용해 오름차순 정렬

후기

- 재귀 함수에 대한 이해가 필요한 문제였다.