[MYSQL/프로그래머스 LV.5] SELECT/멸종위기의 대장균 찾기

문제링크

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

 

문제설명

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


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

제한사항

• 세대에 대해 오름차순
• 모든 세대에는 자식이 없는 개체가 적어도 1개체는 존재 

풀이

이 문제를 풀기위해서 계층적 데이터를 다뤄야 한다고 판단했습니다.

다루기 위해 재귀 공통 테이블 표현식(CTE)을 사용하여 각 데이터의 세대(GENERATION)를 계산하고,

최종적으로 세대별로 데이터의 수를 카운트하는 작업을 수행했습니다.

1. 재귀 CTE 정의 (GENERATION_DATE)

• 첫 번째 SELECT: ECOLI_DATA 테이블에서 PARENT_ID가 NULL인 루트 노드를 선택하고, 이 노드의 GENERATION을 1로 설정합니다.
• UNION ALL: 다음 단계에서는 PARENT_ID가 루트 노드의 ID와 일치하는 자식 노드를 재귀적으로 선택합니다. 이 때 GENERATION은 부모의 GENERATION 값에 1을 더한 값으로 설정됩니다.

2. 최종 SELECT

• WHERE ID NOT IN (...): 최종적으로, 현재 세대의 ID가 자식 노드로 등록된 ID가 아닌 경우만 선택합니다. 즉 리프노드만 선택하여 계산합니다~!

요약

이 문제의 키포인트는 아래와 같습니다

• 계층적 데이터 탐색: 부모-자식 관계를 통해 트리 구조를 탐색하고 각 노드의 깊이(세대)를 계산
• 리프 노드 카운트: 자식 노드가 없는 노드만 선택하여 각 세대의 마지막 노드(리프)의 수를 계산

WITH RECURSIVE GENERATION_DATE AS (
    SELECT   ID 
           , PARENT_ID
           , 1  AS GENERATION
      FROM ECOLI_DATA
     WHERE PARENT_ID IS NULL
    
     UNION ALL

    SELECT   E.ID
           , E.PARENT_ID
           , GENERATION + 1
      FROM ECOLI_DATA E
      JOIN GENERATION_DATE G ON G.ID = E.PARENT_ID
)

SELECT    COUNT(*) AS COUNT
        , GENERATION
  FROM  GENERATION_DATE 
  -- 각 세대별 자식이 없는 대장균의 ID 추출(리프노드)
 WHERE ID NOT IN (SELECT PARENT_ID
                    FROM GENERATION_DATE
                   WHERE PARENT_ID IS NOT NULL)
GROUP BY 2
ORDER BY 2;