[프로그래머스] 특정 세대의 대장균 찾기 (MySQL)

코딩테스트 연습 - 특정 세대의 대장균 찾기

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/301650

프로그래머스

 

문제 설명

대장균이 분화하며 자식 대장균을 생성하는데 3세대 대장균을 구하는 문제이다.

---

문제 풀이

생각 과정

1. 직관적으로 서브쿼리를 사용해서 구할 수 있다고 생각했고

2. JOIN문으로 다시 한번 쿼리를 작성해봤다.

3. 아무리 생각해도 LEVEL4의 난이도가 아닌거 같아 다른 풀이를 보니 재귀를 사용한 방법이 있어서 공부해봤다.

구현

1. 서브쿼리

SELECT ID FROM ECOLI_DATA WHERE PARENT_ID IN 
	(SELECT ID FROM ECOLI_DATA WHERE PARENT_ID IN 
    	(SELECT ID FROM ECOLI_DATA WHERE PARENT_ID IS NULL)
     ) 
ORDER BY ID ASC;

 

2. JOIN

SELECT e1.ID FROM ECOLI_DATA e1
	JOIN ECOLI_DATA e2 ON e1.PARENT_ID = e2.ID
	JOIN ECOLI_DATA e3 ON e2.PARENT_ID = e3.ID
WHERE
	e3.PARENT_ID IS NULL
ORDER BY e1.ID ASC;

 

3. CTE( Common Table Expression )

-- WITH RECURSIVE: 자기 자신을 참조하는 CTE 정의. 트리 구조를 탐색할 때 자주 씀.
WITH RECURSIVE ECOLI_TREE AS (

-- 기본 (Non-Recursive) 파트
SELECT 
    ID,
    PARENT_ID,
    1 GENERATION -- 세대(GENERATION)는 1로 시작함.
FROM 
    ECOLI_DATA
WHERE 
    PARENT_ID IS NULL -- 최상위 노드 (루트 노드)를 찾음.
    
UNION ALL

-- 재귀 (Recursive) 파트
SELECT 
    A.ID,
    A.PARENT_ID,
    B.GENERATION + 1  
FROM 
    ECOLI_DATA A
    INNER JOIN ECOLI_TREE B -- ECOLI_TREE(B)에서 자식 노드(A)를 찾아 계속 붙임.
        ON A.PARENT_ID = B.ID
)

SELECT ID
FROM ECOLI_TREE -- 생성한 재귀중에서 
WHERE GENERATION = 3 -- 3세대 데이터만 추출
ORDER BY ID