[MySQL] 부모의 형질을 모두 가지는 대장균 찾기

문제 설명

대장균들은 일정 주기로 분화하며, 분화를 시작한 개체를 부모 개체, 분화가 되어 나온 개체를 자식 개체라고 합니다. 다음은 실험실에서 배양한 대장균들의 정보를 담은 ECOLI_DATA 테이블입니다. ECOLI_DATA 테이블의 구조는 다음과 같으며, ID, PARENT_ID, SIZE_OF_COLONY, DIFFERENTIATION_DATE, GENOTYPE 은 각각 대장균 개체의 ID, 부모 개체의 ID, 개체의 크기, 분화되어 나온 날짜, 개체의 형질을 나타냅니다.

최초의 대장균 개체의 PARENT_ID 는 NULL 값입니다.

문제

부모의 형질을 모두 보유한 대장균의 ID(ID), 대장균의 형질(GENOTYPE), 부모 대장균의 형질(PARENT_GENOTYPE)을 출력하는 SQL 문을 작성해주세요. 이때 결과는 ID에 대해 오름차순 정렬해주세요.

 

예시

예를 들어 ECOLI_DATA 테이블이 다음과 같다면

ID	PARENT_ID	SIZE_OF_COLONY	DIFFERNETIATION_DATE	GENOTYPE
1	NULL	10	2019/01/01	1
2	1	2	2019/01/01	1
3	1	100	2020/01/01	3
4	2	16	2020/01/01	2
5	4	17	2021/01/01	8
6	3	101	2021/01/01	5
7	2	101	2022/01/01	5
8	6	1	2022/01/01	13

각 대장균 별 형질을 2진수로 나타내면 다음과 같습다.

ID 1 : 1₍₂₎

ID 2 : 1₍₂₎

ID 3 : 11₍₂₎

ID 4 : 10₍₂₎

ID 5 : 1000₍₂₎

ID 6 : 101₍₂₎

ID 7 : 101₍₂₎

ID 8 : 1101₍₂₎

각 대장균 별 보유한 형질을 다음과 같습니다.

ID 1 : 1

ID 2 : 1

ID 3 : 1, 2

ID 4 : 2

ID 5 : 4

ID 6 : 1, 3

ID 7 : 1, 3

ID 8 : 1, 3, 4

각 개체별로 살펴보면 다음과 같습니다.

ID 1 : 최초의 대장균 개체이므로 부모가 없습니다.

ID 2 : 부모는 ID 1 이며 부모의 형질인 1번 형질을 보유하고 있습니다.

ID 3 : 부모는 ID 1 이며 부모의 형질인 1번 형질을 보유하고 있습니다.

ID 4 : 부모는 ID 2 이며 부모의 형질인 1번 형질을 보유하고 있지 않습니다.

ID 5 : 부모는 ID 4 이며 부모의 형질인 2번 형질을 보유하고 있지 않습니다.

ID 6 : 부모는 ID 3 이며 부모의 형질 1, 2번 중 2 번 형질을 보유하고 있지 않습니다.

ID 7 : 부모는 ID 2 이며 부모의 형질인 1번 형질을 보유하고 있습니다.

ID 8 : 부모는 ID 6 이며 부모의 형질 1, 3번을 모두 보유하고 있습니다.

따라서 부모의 형질을 모두 보유한 개체는 ID 2, ID 3, ID 7, ID 8 이다.

---

위 문제를 풀기 위해서는 먼저 자식 ID와 부모 ID의 형질의 비교가 필요하기 때문에 자기 자신의 TABLE을 JOIN 하는 것이 필요하다.

from ECOLI_DATA C join ECOLI_DATA P on C.PARENT_ID = P.ID

이런 식으로 JOIN을 하게 되면 어떻게 되는지 표를 통해 확인해보면 아래와 같다.

이를 해석하면, C와 P라는 두 개의 별칭을 사용해 ECOLI_DATA TABLE을 두 번 불러온 형태이다.

이 때, C.PARENT_ID = P.ID 조건을 통해, 자식 TABLE(C)의 PARENT_ID와 부모 TABLE(P)의 ID가 같은 행을 연결(JOIN)한다.

즉, 같은 TABLE이라도 현재 레코드(C) 입장에서 그 부모 레코드(P)가 어떤 것인지 찾아내기 위해 동일 TABLE과의 JOIN이 필요한 것이다. 이렇게 자식이 어떤 부모 ID를 가지고 있는 지 맵핑한 후, 문제에서 원하는 것을 찾기 위해 비트 연산자를 사용한다.

예시로 자식 ID 3번을 보면, 부모 ID가 1번이고 개체의 형질이 3 이다. ID 1번 개체의 형질은 1이고 3과 1을 이진수로 표현하면,

3 -> 011

1 -> 001

이다. 이를 비교해서 자식이 부모의 형질을 보유하는 지 알아볼 수 있는 방법은 바로 & 연산이다.

011 & 001 -> 001

& 연산을 했을 때 부모 형질을 보유한다면 결과값은 부모의 형질이 나오게 된다.

 

이러한 사실들을 근거로 최종적으로 코드를 작성한다면 아래와 같다.

select C.ID, C.GENOTYPE, P.GENOTYPE as PARENT_GENOTYPE
from ECOLI_DATA C join ECOLI_DATA P on C.PARENT_ID = P.ID
where (C.GENOTYPE & P.GENOTYPE = P.GENOTYPE)
order by C.ID