🚀[SQL 알고리즘 문제 풀이] Programmers : 특정 세대의 대장균 찾기(SELECT)

👇 특정 형질을 가지는 대장균 찾기

프로그래머스

 

🔓 문제 설명

3세대의 대장균의 ID를 출력하는 SQL 문을 작성해주세요.

이때 결과는 대장균의 ID 에 대해 오름차순 정렬해주세요.

 

예시 문제 데이터(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	1	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	6	101	2022-01-01	23
8	6	1	2022-01-01	27

---

⚡SQL Query

기본 정답

SELECT S3.ID AS ID
FROM ECOLI_DATA S1 
    JOIN ECOLI_DATA S2 ON S1.ID = S2.PARENT_ID
    JOIN ECOLI_DATA S3 ON S2.ID = S3.PARENT_ID
WHERE S1.PARENT_ID IS NULL
ORDER BY ID ASC;

 

Oracle 계층형 쿼리 사용

SELECT ID, LEVEL
FROM ECOLI_DATA
-- PARENT_ID가 없는 놈부터 시작해라
START WITH PARENT_ID IS NULL 
-- 이전(PRIOR) ID가 현재의 PARENT_ID인 쪽으로 전개해라
CONNECT BY PRIOR ID = PARENT_ID
-- N세대만 출력
HAVING LEVEL = 3;

 

WITH RECURSIVE 재귀식(MySQL, PostgreSQL) 

WITH RECURSIVE Generation AS (
    -- 1. Anchor: 최상위 부모(1세대) 찾기
    SELECT ID, PARENT_ID, 1 AS LVL
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
    
    UNION ALL
    
    -- 2. Recursive: 자식을 찾으며 세대(LVL) 증가
    SELECT e.ID, e.PARENT_ID, g.LVL + 1
    FROM ECOLI_DATA e
    INNER JOIN Generation g ON e.PARENT_ID = g.ID
)
SELECT ID, LVL FROM Generation 
WHERE LVL = 3; -- N세대 필터링

---

🔎 풀이 설명

1. 3단 조인 구조

• S1: 1세대 (부모가 NULL인 ID)
• S2: 2세대 (S1 을 부모로 둔 ID)
• S3: 3세대 (S2 를 부모도 둔 ID)

2. 조건 매칭:

• WHERE S1.PARENT_ID IS NULL을 통해 최상위 부모임을 보장합니다.

---

💡인사이트

1. 세대(계층형) 문제

•  "N세대" 혹은 "최하위 세대"를 구하라는 문제라면 재귀 쿼리(WITH RECURSIVE, START WITH CONNECT BY)나 계층형 쿼리 문법을 떠올려야 합니다.
• 세대가 고정된 경우 복잡한 계층 함수 보다 Self Join을 여러 번 쓰는 것이 훨씬 빠르고 직관적입니다.
  • Join 순서: 1세대 → 2세대 → 3세대 순서로 조인 조건을 적으면 머릿속으로 가계도를 그리기가 수월합니다.

 

2. 인덱스 설계

• 조인 대상인 ID와 PARENT_ID 양쪽 모두에 인덱스가 있어야 성능 저하 없이 계층 탐색을 할 수 있습니다.