프로그래머스 Lv5 멸종위기의 대장균 찾기(MySQL)

하나 뿐인 Lv5는 도대체 어떤 난이도일까라는 궁금증이 저를 이 문제로 이끌었습니다. 역시나 어렵더군요.

💻 문제

코딩테스트 연습 > SELECT > 멸종위기의 대장균 찾기

• 재귀 쿼리 활용

문제 설명

각 세대별 자식이 없는 개체의 수(COUNT)와 세대(GENERATION)를 출력하는 SQL문을 작성해주세요. 이때 결과는 세대에 대해 오름차순 정렬해주세요. 단, 모든 세대에는 자식이 없는 개체가 적어도 1개체는 존재합니다.

테이블 설명

id, parent_id 칼럼을 가지는데, 최초 대장균 개체의 parent_id는 NULL 값입니다.

---

🔐 풀이

아이디어

세대 정보를 어떻게 관리할 수 있을까에 대해 찾아보다가 WITH RECURSIVE (재귀 쿼리) 찾았습니다.

WITH RECURSIVE로 초기 테이블을 작성하고, 내부에서 해당 테이블을 사용할 수 있으며 UNION을 사용해서 활용합니다.

-- 예시
with recursive tmp as (
	# Non-Recursive 문장
    select 1 as n
    union all -- **
    # Recursive 문장
    select n + 1
    from tmp -- 테이블 사용
    where n < 12 -- 정지 조건
)

select n
from recursive;

이를 사용하여 세대 값을 카운팅합니다. 초기조건은 parent_id가 null일 때 1세대로, 재귀 조건에서는 세대 값을 1씩 증가시켜줍니다.

이때, parent_id 칼럼도 사용해서 세대별 자식이 없는 parent_id를 식별해줍니다.

---

👉 제출 코드

with recursive tmp as (
    select id, parent_id, 1 as generation
    from ecoli_data
    where parent_id is null
    union all
    select s.id, s.parent_id, tmp.generation + 1
    from tmp join ecoli_data s
    on tmp.id = s.parent_id
)

select count(*) count, generation
from tmp
where id not in (
    select distinct parent_id
    from tmp
    where parent_id is not null)
group by generation
order by 2