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

👋😊 인사

안녕하세요!
오늘 새 SQL 문제들이 나와서 바로 맛있게 먹었습니다😋 이번에는 레벨 5문제가 새로 나와서 신나게 풀었습니다.

📍[Lv. 5] 멸종위기의 대장균 찾기

🔗 문제 링크

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

🛠️ 문제 풀이

문제 접근은 다음과 같이 했습니다.

1. ID와 PARENT_ID 간 계층형 쿼리 작성
2. 세대별, PARENT_ID별 개수 구하기
3. 1번의 계층형 테이블의 ID에서 2번의 PARENT_ID이 없는 ROW 구하기
4. 세대별로 그룹화 후 COUNT하기

1. ID와 PARENT_ID 간의 계층형 쿼리 작성
해당 부분은 바로 전 문제인 [Lv. 4 특정 세대의 대장균 찾기]와 공유하는 부분입니다.
Oracle의 경우 CONNECT BY를 쓰고, MYSQL의 경우는 WITH RECURSIVE를 사용하여 재귀형 쿼리로 구현합니다.

WITH RECURSIVE CTE AS (
    #재귀 초기값(1세대=PARENT_ID = NULL인 ROW부터 시작)
    SELECT ID
            ,PARENT_ID
            ,1 AS LEVEL #세대
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
    UNION ALL
    #재귀
    SELECT E.ID
            ,E.PARENT_ID
            , 1+C.LEVEL #세대 증가
    FROM ECOLI_DATA E INNER JOIN CTE C
        ON E.PARENT_ID = C.ID
)

2. 세대 및 PARENT_ID별 개수 구하기
각 세대별 자식이 없는 개체의 수를 구하기 위해서 먼저, 각 세대별, PARENT_ID별로 PARENT_ID와 개수를 구했습니다.

SELECT LEVEL
        ,PARENT_ID
        ,COUNT(PARENT_ID) CNT
FROM CTE
GROUP BY LEVEL, PARENT_ID;

3. 1에서 구한 기존의 계층형 테이블(CTE)의 ID 중에서 2번의 PARENT_ID가 존재하지 않는 ROW를 구합니다.

1번의 결과 테이블은 각 세대와 부모의 정보를 담고 있는 테이블이었습니다.
2번의 결과 테이블은 1번의 테이블에서 세대 및 부모 개체별로 그룹화 하여 각 세대별 PARENT_ID별와 PARENT_ID와 그 개수의 정보를 담고 있는 테이블이었습니다.

해당 문제는 자식이 없는 ROW를 구해야하므로 1번 테이블을 드라이빙 테이블로 두고 1번 테이블의 ID와 2번 테이블의 PARENT_ID를 기준으로 LEFT OUTER JOIN을 합니다.

SELECT *
FROM CTE C LEFT OUTER JOIN (
                            SELECT PARENT_ID
                                    ,COUNT(PARENT_ID) CNT
                            FROM CTE
                            GROUP BY LEVEL, PARENT_ID
                            ) T
ON C.ID = T.PARENT_ID;

4. 세대별로 그룹화 후 COUNT하기
3번의 테이블에서 PARENT_ID가 존재하지 않는 세대별로 그룹화하여 COUNT를 하였습니다.

SELECT COUNT(*) AS 'COUNT'
        ,LEVEL AS GENERATION
FROM CTE C LEFT OUTER JOIN (
                                SELECT PARENT_ID
                                        ,COUNT(PARENT_ID) CNT
                                FROM CTE
                                GROUP BY LEVEL, PARENT_ID
                            ) T
ON C.ID = T.PARENT_ID
WHERE T.PARENT_ID IS NULL
GROUP BY LEVEL
ORDER BY GENERATION;

👾 소스 코드

WITH RECURSIVE CTE AS (
    #재귀 초기값(1세대=PARENT_ID = NULL인 ROW부터 시작)
    SELECT ID
            ,PARENT_ID
            ,1 AS LEVEL 
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
    UNION ALL
    #재귀
    SELECT E.ID
            ,E.PARENT_ID
            ,1+C.LEVEL
    FROM ECOLI_DATA E INNER JOIN CTE C
        ON E.PARENT_ID = C.ID
)

SELECT COUNT(*) AS 'COUNT'
        ,LEVEL AS GENERATION
FROM CTE C LEFT OUTER JOIN (
                                SELECT PARENT_ID
                                        ,COUNT(PARENT_ID) CNT
                                FROM CTE
                                GROUP BY LEVEL, PARENT_ID
                            ) T
ON C.ID = T.PARENT_ID
WHERE T.PARENT_ID IS NULL
GROUP BY LEVEL
ORDER BY GENERATION;

🌅 마무리

🤔 어떤 문제가 있었나요?

각 세대별 대장균 개체의 부모 개체의 존재여부와 개수를 세는 부분(3번)의 쿼리를 짜는데 꽤 긴 시간을 소요했습니다.

🤔 어떻게 해결했고 무엇을 알았나요?

차근차근 문제를 분할하여 풀이계획을 세워서 한 단계씩 풀어나갔습니다.

👋😊 인사

부족한 글 읽어주셔서 감사합니다.
잘못된 부분 혹은 개선할만한 부분에 대한 댓글 항상 환영합니다.