[SQL] 프로그래머스 - 특정 세대의 대장균 찾기

문제

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

프로그래머스

---

해결

나는 부모ID가 NULL인 대장균의 ID 찾고,

그 대장균의 ID가 부모 ID인 대장균의 ID찾고

그 대장균의 ID가 부모 ID인 대장균의 ID를 찾으면 된다고 생각했다.

 

그래서 where 조건에 서브쿼리를 3번 작성해봤다.

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;

 

그리고 결과는 통과였다.

직관적으로만 쿼리를 작성했는데 너무 간단하게 통과가 돼서 다소 놀랬다.

분명 효율적인 쿼리는 아닐 것 같았기 때문이다. (시간초과 문제로 실패할 줄 알았는데...)

그래서 다른 사람들은 어떻게 해결했나 궁금해서 찾아 봤다.

 

찾아본 것들 중에 직관적이면서 효율적인 쿼리를 찾았다.

(ref. https://eunsun-zizone-zzang.tistory.com/134)

select F.ID
	from ECOLI_DATA AS F
	join ECOLI_DATA AS S on F.PARENT_ID = S.ID
	join ECOLI_DATA AS T on S.PARENT_ID = T.ID
where T.PARENT_ID is NULL
order by F.ID ASC

 

join절을 사용해서 해결한 것이였다.

 

내 쿼리는 PARENT_ID를 비교할 때마다 서브쿼리를 실행하기 때문에 시간복잡도로 보면 O(n^3)이고,

join을 활용한 쿼리는 O(n)이기 때문이다!

 

 

다음엔 더 잘 할 수 있겠지.ㅎㅎ

 

---

ref.

https://latewalk.tistory.com/278

JOIN과 서브쿼리의 차이