[SQL]특정 세대의 대장균 찾기 - SQL 고득점 Kit

문제

코딩테스트 연습 - 특정 세대의 대장균 찾기 | 프로그래머스 스쿨

프로그래머스

풀이 - 단순하게 푸는 방식

WITH FIRST_CTE AS (
    SELECT ID 
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
),
SECOND_CTE AS (
    SELECT ID 
    FROM ECOLI_DATA
    WHERE PARENT_ID IN (SELECT * FROM FIRST_CTE)
)
SELECT ID 
FROM ECOLI_DATA
WHERE PARENT_ID IN (SELECT * FROM SECOND_CTE)
ORDER BY ID

이 문제는 결국 쿼리를 계층형으로 여러 번 실행시킨 뒤에 찾아야 한다.

여기서 알아야 하는 개념이 바로 Common Table Expression(CTE)이다.

CTE는 임시 결과 테이블을 만드는 것이다.

WITH이라는 키워드를 사용해서 만들면 된다.

여기서는 FIRST_CTE를 만들고 그 다음 SECOND_CTE를 만든다.

 

그러면 어떻게 푸는지 보면 다음과 같다.

결국 3세대의 대장균의 찾는다는 말은 PARENT_ID를 3번 타고 들어간 값을 찾는 것이다.

그러면 먼저 1세대 대장균을 찾는다.

WITH FIRST_CTE AS (
    SELECT ID 
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
),

 

문제 예시에서 NULL이 1세대라고 했으므로 FIRST_CTE에 NULL인 것을 찾아서 넣어둔다.

 

SECOND_CTE AS (
    SELECT ID 
    FROM ECOLI_DATA
    WHERE PARENT_ID IN (SELECT * FROM FIRST_CTE)
)

그 뒤엔 FIRST_CTE에서 찾은 ID 값들을 PARENT_ID로 가지고 있는 행들을 SECOND_CTE에 저장한다.

in 키워드는 in 안에 들어있는 값 중 하나라도 들어있으면 그 행을 반환한다.

예를 들어, where id in (1,2,3,4) 이렇게 한다면, id가 1,2,3,4 중에 하나인 행들을 반환한다.

 

이렇게 FIRST_CTE와 SECOND_CTE 임시 테이블을 만들었다.

그러면 3세대는 어떻게 찾을까?

간단하다.

SELECT ID 
FROM ECOLI_DATA
WHERE PARENT_ID IN (SELECT * FROM SECOND_CTE)
ORDER BY ID

SECOND_CTE이 가지고 있는 PARENT_ID에 속하는 값을 찾으면 그만이다.

 

풀이 - 재귀를 이용해서 푸는 방식

WITH RECURSIVE Hierarchy_CTE AS (
    -- 초기 루트 노드 선택
    SELECT ID, PARENT_ID, 1 AS LEVEL
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
    UNION ALL
    -- 재귀적으로 자식 노드 찾기
    SELECT E.ID, E.PARENT_ID, H.LEVEL + 1
    FROM ECOLI_DATA E
    INNER JOIN Hierarchy_CTE H ON E.PARENT_ID = H.ID
)
SELECT ID
FROM Hierarchy_CTE
WHERE LEVEL = 3 -- 원하는 계층 선택
ORDER BY ID;

프로그래밍 언어에 있는 재귀 함수와 비슷한 역할을 하는 WITH RECURSIVE이다.

 

    SELECT ID, PARENT_ID, 1 AS LEVEL
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL

위 부분은 Anchor Query 라고 하고 초기 값을 설정하는 곳이다.

    UNION ALL

위 키워드로 재귀하고 초기값이 갈린다고 보면 된다.

결국 계속해서 UNION 연산을 진행하게 되는데, ALL을 사용하면 중복 제거를 할 수 있다.

    SELECT E.ID, E.PARENT_ID, H.LEVEL + 1
    FROM ECOLI_DATA E
    INNER JOIN Hierarchy_CTE H ON E.PARENT_ID = H.ID

이 부분은 계속해서 불러와지는 쿼리로

H.LEVEL + 1을 한 뒤, 아까처럼 PARENT_ID를 비교하여 자식을 찾는다.

그렇게 모든 테이블이 만들어지게 된다.

SELECT ID
FROM Hierarchy_CTE
WHERE LEVEL = 3 -- 원하는 계층 선택
ORDER BY ID;

그 뒤에 레벨을 필터링하면 결과값이 완성된다.

 

참고로 재귀 부분을 모두 진행하게 되면 다음과 같은 테이블이 만들어진다.

여기서 level = 3만 가져가면 우리가 원하는 값을 구할 수 있게 된다.