[Python] 백준 20502번 : Gum색

태그 기반 검색 최적화: O(N²)에서 O(1)로 성능 개선하기

해당 글은 백준사이트의 20502번 문제를 풀고 배운 내용을 정리한 글입니다.

문제 url: https://www.acmicpc.net/problem/20502

 

백준 20502번 문제를 풀면서 리스트(list)와 깊은 복사를 사용한 풀이 → dict를 활용한 자료구조 개선 → remove() 대안 도출 과정으로 최적화한 경험을 공유하려 한다.

---

1️⃣ 처음에는 익숙한 list와 깊은 복사를 사용했다

문제를 처음 접했을 때, 태그를 포함하는 개체들을 리스트(list)로 저장하는 방식이 직관적이라고 생각했다.
따라서 개체들의 랭크(중요도) 정보를 저장하고, 각 태그별 개체 목록을 리스트로 관리하는 방식으로 접근했다.

이 과정에서 깊은 복사(copy.deepcopy())를 사용하여 랭크 값을 보존하면서 필터링하는 방식을 사용했다.

 

import copy

# 게시글의 수 N, 키워드의 수 M
N, M = map(int, input().split())

# 게시글의 순위 rank, rank대로 게시글 번호 정렬한 new_rank
rank = list(map(int, input().split()))
new_rank = []
for n in range(1, N+1):
    new_rank.append(rank.index(n) + 1)

# 각 게시글의 키워드 board
board = [[]]
for n in range(1, N+1):
    lst = list(map(int, input().split()))
    board.append(lst[1:])

# 질문 수 Q
Q = int(input())
for _ in range(Q):
	# 찾는 키워드 k
    k = int(input())
    ans = copy.deepcopy(new_rank)
    for n in range(1, N+1):
        if k not in board[n]:
           ans.remove(n)
    if ans:
        print(*ans)
    else:
        print(-1)

🚨 이 방식의 문제점

✅ list를 사용하여 직관적인 구현이 가능
❌ remove() 연산이 포함되어 있어 O(N²) 가능성 발생
❌ copy.deepcopy()로 인한 불필요한 메모리 사용 증가

---

2️⃣ dict를 활용한 자료구조 개선

깊은 복사를 사용한 기존 방법은 연산량이 많고 메모리 사용량도 컸다.
개선을 위해, 태그별로 개체들을 저장하는 리스트를 dict(defaultdict)로 변환했다.

💡 왜 dict를 사용했을까?

• dict는 태그(키) 별로 개체 목록을 빠르게 저장하고 조회할 수 있음
• 특정 태그를 포함하는 개체들을 찾을 때 O(1)에 가깝게 조회 가능
• list 기반 접근보다 더 효율적인 구조를 가질 수 있음

 

# 각 태그별로 dict를 사용해 개체 번호를 저장하고 관리하는 방식으로 개선
import copy
from collections import defaultdict

N, M = map(int, input().split())
rank = list(map(int, input().split()))
new_rank = []
for n in range(1, N+1):
    new_rank.append(rank.index(n) + 1)

# board의 key는 키워드 k, value는 게시글 n
board = defaultdict(list)
for n in range(1, N+1):
    lst = list(map(int, input().split()))[1:]
    for k in lst:
        board[k].append(n)

Q = int(input())
for _ in range(Q):
    k = int(input())
    if board[k]:
        ans = copy.deepcopy(new_rank)
        for x in new_rank:
            if x not in board[k]:
               ans.remove(x)
        print(*ans)
    else:
        print(-1)

 

🚨 이 방식의 개선점

✅ dict(defaultdict) 사용으로 조회 속도 개선 (O(N) → O(1))
✅ copy.deepcopy() 제거로 메모리 절약
❌ 여전히 remove() 사용으로 인한 비효율 존재

---

3️⃣ remove() 대안 도입으로 최적화

이전 개선을 통해 dict를 사용해 태그별 개체들을 빠르게 조회할 수 있었지만,
여전히 remove() 연산이 리스트 내 요소를 삭제할 때 O(N) 연산을 유발하여 성능 저하 가능성이 존재했다.

💡 최적화 방법

1. 사전 정렬을 활용하여 필터링 연산을 없앰
2. 개체별 중요도를 기준으로 미리 정렬하여 조회만 수행 (O(1))
3. 각 태그의 개체 목록을 정렬한 후, 질의 시 바로 출력

from collections import defaultdict

N, M = map(int, input().split())
# rank 수정
rank = [0] + list(map(int, input().split()))

board = defaultdict(list)
for n in range(1, N+1):
    lst = list(map(int, input().split()))[1:]
    for k in lst:
        board[k].append(n)

# lambda를 통해 게시글 rank 수정
for k in board:
    board[k].sort(key=lambda x: rank[x])

Q = int(input())
for _ in range(Q):
    k = int(input())
    # remove()함수 제거
    if board[k]:
        print(*board[k])
    else:
        print(-1)

 

이렇게 하면,
✅ 정렬은 미리 수행하므로 O(N log N) (한 번만 수행)
✅ 이후 질의는 O(1)에 가깝게 수행 가능
✅ remove()를 사용하지 않으므로 O(N²) 가능성 제거

---

4️⃣ 최적화된 코드 & 성능 비교

최종적으로, 리스트 기반 풀이 → dict 도입 → remove() 제거 및 사전 정렬 방식을 통해
O(N²)에서 O(N log N) + O(1)으로 최적화되었다.

단계 사용한 자료구조 시간 복잡도 주요 문제점 개선 여부

1️⃣ 리스트 & 깊은 복사	list + copy.deepcopy()	O(N²)	remove() 사용으로 성능 저하	❌
2️⃣ dict(defaultdict) 도입	defaultdict(list)	O(N²)	여전히 remove() 사용	❌
3️⃣ remove() 제거 및 정렬 적용	defaultdict(list) + sort()	O(N log N) + O(1)	미리 정렬하여 질의 최적화	✅

✅ 최적화된 코드에서는 remove() 없이 미리 정렬하여 O(1)로 검색 가능

---

5️⃣ 마무리 및 배운 점

이번 문제를 풀면서 처음에는 익숙한 방식(list & deepcopy)을 사용했지만, 점진적인 개선을 통해 성능을 최적화할 수 있었다.
다음과 같은 점을 배울 수 있었다.

📌 배운 점

1. 리스트 기반 접근 방식은 직관적이지만 성능이 좋지 않을 수 있음
2. dict를 사용하면 데이터를 더 빠르게 조회 가능
3. 비효율적인 연산(remove())은 피하고, 미리 정렬을 활용하는 것이 좋음
4. 사전 정렬을 활용하면 질의 속도를 대폭 향상할 수 있음

📌 비슷한 유형의 문제 추천

• 백준 18870번 좌표 압축 → 리스트와 딕셔너리 활용
• 백준 1764번 듣보잡 → 딕셔너리를 사용한 빠른 검색

---

✅ 최종 정리

🔹 리스트 기반 접근 → dict 사용 → remove() 제거 및 정렬 적용 순으로 점진적인 개선
🔹 O(N²) → O(N log N) + O(1)로 성능 개선
🔹 불필요한 연산을 없애는 것이 핵심 최적화 방법

이런 문제를 접할 때 초기 코드가 정답이 아니라, 개선 과정을 통해 최적의 코드로 발전시켜야 한다는 점을 다시 한번 깨달았다.
이 글이 비슷한 고민을 하고 있는 사람들에게 도움이 되었으면 좋겠다! 🚀🔥