백준 1202 보석 도둑 문제 풀이
문제 파악하기
모든 가방에 대해, 각 가방이 담을 수 있는 무게 한도 내에서, 가장 가치가 높은 보석을 담도록 하는 문제입니다.
가방이라는 단어가 있지만 한 가방에 한 개의 보석만 담을 수 있으므로 냅색 문제는 아닙니다.
문제 풀어보기
각 가방이 허용하는 무게 범위 내에서 최대의 가치를 지닌 보석을 선택하면 되므로, 모든 값이 잘 정렬되어있다면 값을 잘 고르는 것으로 문제를 해결할 수 있습니다.
가방의 허용 무게가 크면 클수록 선택에 있어 고려해야 할 보석의 개수가 많아집니다. 만약 가벼우면서 가치가 높은 보석이 있다면, 가방의 허용 무게가 큰 것부터 보석을 선택하는 것은 적절한 해답이 되지 못할 것입니다.
| 배낭(허용 무게) | 선택된 보석의 무게 | 선택된 보석의 가치 |
|---|---|---|
| 10 | 1 | 10 |
| 1 | - | - |
| - | 3 | 3 |
구체적인 구현 내용에 따라 달라질 수 있지만, 일반적으로 위 상황에서 허용 무게가 큰 것부터 보석을 선택하면 허용 무게가 10인 배낭에 (무게, 가치) = (1, 10) 인 보석을 넣고 처리가 종료될 가능성이 높습니다. 위 상황에서 적절한 답은 허용 무게가 10인 배낭에 (무게, 가치) = (3, 3)인 보석을, 허용 무게가 1인 배낭에 (무게, 가치) = (1, 10)인 보석을 넣는 것입니다.
배낭을 허용 무게가 작은 것부터 처리하니 보석 역시 작은 것부터 처리하는 것이 구현에 용이할 것입니다.
1
2
3
4
5
6
7
jewels: list[tuple[int]] = [(m1, v1), (m2, v2), ...]
bags: list[int]
# (m, v)일 때, 파이썬: m 기준으로 우선 정렬 후 v 기준 정렬
jewels.sort()
bags.sort()
1
2
3
4
5
6
7
def compute(n: int, k: int, jewels: list[tuple[int]], bags: list[int]) -> int:
result: int = 0
targets: list[tuple[int]] = []
for bag in bags:
while jewels and bag >= jewels[0][0]:
targets.append(jewels.pop(0)[1])
...
위와 같이 구현하면 targets 에 현재 처리 중인 가방(bag)이 담을 수 있는 보석의 가치 값이 추가될 것입니다. 하지만 보석 리스트(jewels: list[tuple[int]])는 가치가 아니라 무게를 기준으로 정렬되었습니다. 선택 가능한 보석들 중 가장 높은 보석을 선택하기 위해서는 추가적인 처리 코드가 필요할 것입니다.
1
2
targets.sort()
targets.pop()
문제는 매 가방마다 선택 가능한 보석의 개수가 달라지므로, 매 가방마다 선택 가능한 보석의 최대 가치를 갱신해야 합니다. 이러한 구현 방식은 최대값을 구할때마다 큰 오버헤드를 발생시킬 수 있습니다.
1
2
3
4
5
6
7
8
9
def compute(n: int, k: int, jewels: list[tuple[int]], bags: list[int]) -> int:
...
for bag in bags:
while jewels and bag >= jewels[0][0]:
...
targets.sort()
if targets:
result += targets.pop()
...
우선순위 큐
문제 조건에 따르면 보석은 최대 1백만개, 가방은 최대 1억개 주어질 수 있습니다. 다행히도, 위 구현 방식은 이중포문(O(n^2))으로 구현된 것은 아니어서 긴 러닝타임을 걱정해야 하는 것은 아닙니다. 하지만 입력 데이터는 제한 시간에 비해 여전히 지나치게 큽니다.
우선순위 큐는 아이템의 추가/삭제가 잦을 때, 최대값/최소값을 빠르게 구하는데 용이하게 사용될 수 있습니다.
파이썬은 우선순위 큐의 구현 중 하나로 힙 큐(heapq)모듈을 제공합니다. 이 모듈은 파이썬의 일반 리스트에 적용할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
from heapq import heappush, heappop
...
...
targets: list[tuple[int]] = []
for bag in bags:
while jewels and bag >= jewels[0][0]:
heappush(targets, -(jewels.pop(0)[1]))
if targets:
result += heappop(targets)
...
...
파이썬의 list.pop(0)은 선형 시간(O(n))이 소모되므로 좋지 않은 선택입니다. 다행히 힙 큐 모듈을 일반 리스트에 사용할 수 있으므로 heappop을 사용할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
from heapq import heappush, heappop
def compute(n: int, k: int, jewels: list[tuple[int]], bags: list[int]) -> int:
...
targets: list[tuple[int]] = []
for bag in bags:
while jewels and bag >= jewels[0][0]:
heappush(targets, -(heappop(jewels)[1]))
if targets:
result += heappop(targets)
elif not jewels:
break
...