🚀[SQL 알고리즘 문제 풀이] Programmers : 멸종위기의 대장균 찾기(SELECT)

👇 멸종위기의 대장균 찾기

프로그래머스

 

🔓 문제 설명

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

---

⚡SQL Query

WITH RECURSIVE 재귀식(MySQL, PostgreSQL) 

WITH RECURSIVE GenerationCTE AS (
    -- 1단계: 1세대 추출 (Anchor)
    SELECT ID, PARENT_ID, 1 AS GENERATION
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
    
    UNION ALL
    
    -- 2단계: 재귀적으로 다음 세대 계산 (Recursive)
    SELECT e.ID, e.PARENT_ID, g.GENERATION + 1
    FROM ECOLI_DATA e
    INNER JOIN GenerationCTE g ON e.PARENT_ID = g.ID
)
SELECT COUNT(*) AS COUNT, GENERATION
FROM GenerationCTE
WHERE ID NOT IN (
    -- 자식이 있는 ID(즉, 누군가의 PARENT_ID인 ID)를 제외
    SELECT DISTINCT PARENT_ID 
    FROM ECOLI_DATA 
    WHERE PARENT_ID IS NOT NULL
)
GROUP BY GENERATION
ORDER BY GENERATION ASC;

 

Oracle 계층형 쿼리 사용

SELECT COUNT(*) AS COUNT, LEVEL AS GENERATION
FROM ECOLI_DATA
WHERE CONNECT_BY_ISLEAF = 1 -- 자식이 없는 개체만 필터링
START WITH PARENT_ID IS NULL
CONNECT BY PRIOR ID = PARENT_ID
GROUP BY LEVEL
ORDER BY LEVEL ASC;

---

🔎 풀이 설명

1. 재귀 쿼리 작성

• WITH RECURSIVE를 통해 모든 개체의 세대를 구합니다.

2. 자식 없는 개체 필터링

• WHERE ID NOT IN (SELECT PARENT_ID ...) 조건을 사용하여 자식 없는 개체를 구합니다.

3. 그룹화 및 정렬

---

💡인사이트

1. 오라클 CONNECT_BY_ISLEAF의 효율성

• Oracle에서 이 기능을 사용하면 별도의 서브쿼리 없이 계층 탐색 중에 즉시 자식 존재 여부를 판단하므로 성능상 매우 유리합니다.

2. MySQL 재귀 쿼리

• MySQL의 재귀 쿼리는 내부적으로 Work Table을 사용하기 때문에 데이터가 방대할 경우 재귀의 깊이만큼 반복적으로 조인이 발생하여 성능 부하가 심해집니다.

3. Anti-Join 최적화

• NOT IN 대신 NOT EXISTS를 사용하면 옵티마이저가 Anti-Join으로 변환하여 더 효율적인 실행 계획을 세울 수 있습니다.