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

코딩테스트를 풀며 재귀쿼리를 처음 보았다. 우선 잘 모르는 쿼리 문법이기에 다른 분의 쿼리를 보며 뜯어보고 이해하는 과정을 거쳤다. 

이렇게 SQL 코딩테스트에서 만점을 받는 미래의 나를 상상한다. 

 

우선 재귀 쿼리란 

데이터베이스에서 자기 참조 데이터 또는 계층적 데이터를 조회할 때 사용되는 쿼리라고 한다. MySQL 에서는 WITH RECURSIVE 라는 키워드를 사용해 재귀 쿼리를 작성할 수 있고 이번 문제 또한 이 문법을 활용해서 작성하였다.
이를 통해 부모-자식 관계를 갖는 계층적 데이터를 작성하고 추출할 수 있다.

 

WITH RECURSIVE CTE (컬럼1, 컬럼2, ...) AS 
( SELECT 
  FROM 
  WHERE 
  
  UNION ALL 
  
  --- 재귀적으로 호출되어야 하는 부분을 작성한다. 
  SELECT 
  FROM 
  JOIN CTE ON 
  
  ) 
  
  SELECT * 
  FROM CTE ;

 

 

WITH RECURSIVE GenerationCTE AS (
    SELECT ID 
         , PARENT_ID 
         , 1 AS Generation 
    FROM ECOLI_DATA 
    WHERE PARENT_ID IS NULL

- PARENT_ID IS NULL 이라는 조건을 통해 루트 노드(최상위 계층)를 가져온다.

- Generation 은 세대로 1로 시작

 

    UNION ALL 
    
    SELECT e.ID, e.PARENT_ID, g.Generation + 1 as Generation 
    FROM ECOLI_DATA e 
    JOIN GenerationCTE g ON e.PARENT_ID = g.ID
)

- JOIN GenerationCTE g ON e.PARENT_ID = g.ID 는 자식노드를 부모 노드와 연결하여 다음 계층으로 확장하도록 한다. 

** Generation + 1 을 하여 각 자식 노드의 세대를 하나씩 증가시키는 컬럼을 추가한다. ** 

 

WHERE ID NOT IN (
        SELECT DISTINCT parent_id 
        FROM GenerationCTE
        WHERE parent_id IS NOT NULL)

 

조건은 parent_id 가 NULL 이 아닌 parent id 를 1차적으로 거른 후 parent_id 가 있는 ID 는 제외한다. 

이렇게 되면, 어떤 노드의 부모로도 등장하지 않은 노드를 선택할 수 있게 된다. 

 

마지막으로 각 세대별로 COUNT 를 수행한다. 

SELECT COUNT(*) AS COUNT, Generation 
FROM GenerationCTE 
GROUP BY Generation 
ORDER BY 2

 

전체 코드 

-- 코드를 작성해주세요

WITH RECURSIVE GenerationCTE AS (
    SELECT ID 
         , PARENT_ID 
         , 1 AS Generation 
    FROM ECOLI_DATA 
    WHERE PARENT_ID IS NULL
    
    UNION ALL 
    SELECT e.ID , e.PARENT_ID , g.Generation + 1 as Generation 
    FROM ECOLI_DATA e 
    JOIN GenerationCTE g ON e.PARENT_ID = g.ID)


SELECT count(*) as COUNT 
        , Generation 
FROM GenerationCTE 
WHERE ID not in (
        select distinct parent_id 
        from GenerationCTE
        where parent_id is not null)
GROUP BY generation 
order by 2

 

 

혼자 작성하진 못하고 재귀 쿼리 답변을 보며 뜯어봄으로 이해를 완료하였다. 바로 내일 동일한 문제를 스스로 풀어보며 체화시켜야겠다!