[SQL TEST 22일차] SELECT, LV.2 : 부모의 형질을 모두 가지는 대장균 찾기

코딩테스트_프로그래머스

주제 : 부모의 형질을 모두 가지는 대장균 찾기

범위: Select

레벨: Lv.2

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

프로그래머스

---

문제 설명
대장균들은 일정 주기로 분화하며, 분화를 시작한 개체를 부모 개체, 분화가 되어 나온 개체를 자식 개체라고 합니다.
다음은 실험실에서 배양한 대장균들의 정보를 담은 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 테이블이 다음과 같다면

 

각 대장균 별 형질을 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 에 대해 오름차순 정렬하면 다음과 같아야 합니다.

---

#답

SELECT A.ID, A.GENOTYPE, B.GENOTYPE AS PARENT_GENOTYPE
FROM ECOLI_DATA A
JOIN ECOLI_DATA B ON A.PARENT_ID = B.ID
WHERE A.GENOTYPE & B.GENOTYPE = B.GENOTYPE
ORDER BY A.ID;

• 같은 table인데 굳이 self join 하는 이유?
  • 한 table에서 부모 정보, 자식 정보도 동시에 보고 싶기 때문. 
    자식 행 A과 부모 행 B 서로 연결 필요 => self join 
• A가 자식 테이블, B가 부모 테이블인데, ON A.PARENT_ID = B.ID ?
  
  • A.PARENT_ID = 자식의 부모가 누구 ? B.ID = 부모 자신 번호

 

#설명

핵심 아이디어 — 비트 관점으로 이해

• 어떤 정수의 이진표현에서 1인 비트는 그 형질을 보유했다는 뜻
  • 예: GENOTYPE = 5 → 이진 101 → 1번 형질(LSB), 3번 형질 보유
• 부모의 모든 형질을 자식이 가지고 있는지 확인하려면, 부모의 비트들이 자식에도 모두 포함되어야 함
• 이걸 검사하는 쉬운 방법: 비트 AND 연산 (A & B)을 사용
  • A & B = B 이면, B(부모)의 1비트는 모두 A(자식)에도 있다는 뜻

10진수(Decimal)	2진수(Binary)	비트 자리 설명 (1=형질 보유)
1	0001	1번 형질 보유
2	0010	2번 형질 보유
3	0011	1, 2번 형질 보유
4	0100	3번 형질 보유
5	0101	1, 3번 형질 보유
6	0110	2, 3번 형질 보유
7	0111	1, 2, 3번 형질 보유
8	1000	4번 형질 보유
9	1001	1, 4번 형질 보유
10	1010	2, 4번 형질 보유
11	1011	1, 2, 4번 형질 보유
12	1100	3, 4번 형질 보유
13	1101	1, 3, 4번 형질 보유

 

예를 들어

• 13 (1101₂)은 1·3·4번 형질을 모두 가지고 있고,
• 6 (0110₂)은 2·3번 형질만 가지고 있는 거