[SQL_Q] 업그레이드 할 수 없는 아이템 구하기 ( exists )

Hyunjun Kim·2025년 10월 26일

SQL

목록 보기

89/90

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

1. 문제

문제 설명
어느 한 게임에서 사용되는 아이템들은 업그레이드가 가능합니다.
'ITEM_A'->'ITEM_B'와 같이 업그레이드가 가능할 때
'ITEM_A'를 'ITEM_B'의 PARENT 아이템,
PARENT 아이템이 없는 아이템을 ROOT 아이템이라고 합니다.

예를 들어 'ITEM_A'->'ITEM_B'->'ITEM_C' 와 같이 업그레이드가 가능한 아이템이 있다면
'ITEM_C'의 PARENT 아이템은 'ITEM_B'
'ITEM_B'의 PARENT 아이템은 'ITEM_A'
ROOT 아이템은 'ITEM_A'가 됩니다.

다음은 해당 게임에서 사용되는 아이템 정보를 담은 ITEM_INFO 테이블과 아이템 관계를 나타낸 ITEM_TREE 테이블입니다.

ITEM_INFO 테이블은 다음과 같으며, ITEM_ID, ITEM_NAME, RARITY, PRICE는 각각 아이템 ID, 아이템 명, 아이템의 희귀도, 아이템의 가격을 나타냅니다.

Column_name	Type	Nullable
ITEM_ID	INTEGER	FALSE
ITEM_NAME	VARCHAR(N)	FALSE
RARITY	INTEGER	FALSE
PRICE	INTEGER	FALSE

ITEM_TREE 테이블은 다음과 같으며, ITEM_ID, PARENT_ITEM_ID는 각각 아이템 ID, PARENT 아이템의 ID를 나타냅니다.

Column_name	Type	Nullable
ITEM_ID	INTEGER	FALSE
PARENT_ITEM_ID	INTEGER	TRUE

단, 각 아이템들은 오직 하나의 PARENT 아이템 ID 를 가지며, ROOT 아이템의 PARENT 아이템 ID 는 NULL 입니다.

ROOT 아이템이 없는 경우는 존재하지 않습니다.

1.1 문제

더 이상 업그레이드할 수 없는 아이템의 아이템 ID(ITEM_ID), 아이템 명(ITEM_NAME), 아이템의 희귀도(RARITY)를 출력하는 SQL 문을 작성해 주세요. 이때 결과는 아이템 ID를 기준으로 내림차순 정렬해 주세요.

예시

예를 들어 ITEM_INFO 테이블이 다음과 같고

ITEM_ID	ITEM_NAME	RARITY	PRICE
0	ITEM_A	RARE	10000
1	ITEM_B	RARE	9000
2	ITEM_C	LEGEND	11000
3	ITEM_D	RARE	10000
4	ITEM_E	RARE	12000

ITEM_TREE 테이블이 다음과 같다면

ITEM_ID	PARENT_ITEM_ID
0	NULL
1	0
2	0
3	1
4	1

'ITEM_A' 는 'ITEM_B', 'ITEM_C' 로 업그레이드가 가능하며 'ITEM_B' 는 'ITEM_D', 'ITEM_E' 로 업그레이드가 가능합니다. 'ITEM_C', 'ITEM_D', 'ITEM_E' 는 더 이상 업그레이드가 가능하지 않으므로 결과는 다음과 같이 나와야 합니다.

ITEM_ID	ITEM_NAME	RARITY
4	ITEM_E	RARE
3	ITEM_D	RARE
2	ITEM_C	LEGEND

2. 문제 풀이

2.1 내 풀이

select a.ITEM_ID, ITEM_NAME, RARITY
from  (
    select ITEM_ID
    from ITEM_TREE t1
    where not exists (
        select *
        from ITEM_TREE t2
        where t1.ITEM_ID = t2.PARENT_ITEM_ID
    ))as a
join ITEM_INFO i
on a.ITEM_ID = i.ITEM_ID
order by 1 desc

3. 쿼리 최적화

3.1 최적화 방법

1) NOT EXISTS 유지 + JOIN 단순화 방법

SELECT t.ITEM_ID, i.ITEM_NAME, i.RARITY
FROM ITEM_TREE t
JOIN ITEM_INFO i
ON t.ITEM_ID = i.ITEM_ID
WHERE NOT EXISTS (
    SELECT 1
    FROM ITEM_TREE c
    WHERE c.PARENT_ITEM_ID = t.ITEM_ID
)
ORDER BY t.ITEM_ID DESC;

서브쿼리를 inline으로 바로 WHERE에 사용
별도의 alias(a)를 만들 필요 없음
인덱스가 있다면 NOT EXISTS도 매우 효율적임
- PARENT_ITEM_ID에 인덱스 존재 시 MySQL은 semi-join 최적화 수행

2) LEFT JOIN 방법

SELECT t.ITEM_ID, i.ITEM_NAME, i.RARITY
FROM ITEM_TREE t
LEFT JOIN ITEM_TREE c
  ON t.ITEM_ID = c.PARENT_ITEM_ID
JOIN ITEM_INFO i
  ON t.ITEM_ID = i.ITEM_ID
WHERE c.ITEM_ID IS NULL
ORDER BY t.ITEM_ID DESC;

서브쿼리 제거 → 쿼리 읽기 직관적
LEFT JOIN으로 자식 없는 노드 바로 필터링 → MySQL 최적화 엔진이 효율적으로 처리 가능
인덱스 활용 가능
- ITEM_TREE.PARENT_ITEM_ID에 인덱스 존재 시 LEFT JOIN 성능 좋음
- ITEM_INFO.ITEM_ID에 PK 또는 인덱스 있어야 조인 효율적

3.2 추천 인덱스

컬럼	추천 인덱스	이유
ITEM_TREE.PARENT_ITEM_ID	INDEX	자식 존재 여부 확인 빠름
ITEM_INFO.ITEM_ID	PRIMARY KEY	JOIN 효율
ITEM_TREE.ITEM_ID	PRIMARY KEY	조인 및 ORDER BY 효율

3.3 장 단점 비교

방식	장점	단점
NOT EXISTS	- 인덱스 활용 시 매우 빠름 - NULL 처리 안정적	- 서브쿼리 구조 때문에 시각적 복잡
LEFT JOIN + IS NULL	- 직관적 - 다른 컬럼과 바로 조인 용이	- 자식 테이블이 큰 경우 메모리 사용 증가