❓1202번 : 보석 도둑
〽️ 문제 요약
보석의 가격과 무게가 보석의 개수 N개 만큼 주어지고, 하나의 가방이 담을 수 있는 무게가 가방의 개수 K개 만큼 주어질 때 하나의 가방에는 하나의 보석을 넣을 수 있는 경우 가방에 담을 수 있는 보석 가격의 최대값을 구하면 되는 문제
🤨 접근법
고를 수 있는 가장 최선의 선택은 비싼 보석을 가격 순서대로 가방의 수만큼 모두 담아내는 것이다. 이를 위해 보석의 정보와 가방들을 받고 보석은 가격에 대해 내림차순, 가방은 담을 수 있는 무게에 대해 오름차순으로 정렬하였다.
다음, 가방을 순회하며 담을 수 있는 보석 중 가장 비싼 보석을 담는다. 이미 보석들이 가격을 기준으로 정렬되어있으므로 처음으로 담긴 보석이 담을 수 있는 가장 비싼 보석이다.
이 방법으로 모든 가방에 보석이 담길 때 까지 진행하면 답을 얻어낼 수 있다. 하지만 시간초과가 발생한다. 그리디한 방법이지만 부르트 포스에 가까운 방법이긴 하다.
이를 해결하기 위해서는 힙을 활용한 우선순위 큐로 이 과정을 구현해야 한다. 힙을 push하고 pop하는 시간 복잡도는 logN이므로 더욱 효율적으로 그리디 및 우선순위 문제를 해결할 수 있다.
보석들과 가방들에 대한 정보를 받을 때, 받은 후 정렬을 수행하지 않고 최소 힙에 넣어줌으로써 최소 값을 pop하여 활용하자.
가방을 순회하며 가방에 대한 heap에서 최소 무게를 담을 수 있는 가방을 pop한다. 해당 가방에 대해서 무게 상으로 담을 수 있는 보석들의 가격만 별도의 힙에 push하자. 이 힙은 max heap으로 구현하여 pop시 해당 힙의 가장 높은 가격 순으로 뽑을 수 있도록 한다. 담을 수 있는 보석을 모두 담으면 하나를 pop하여 카운트 한다. 해당 가방이 담을 수 있는 가장 최고 가격의 보석이다.
그 다음 가방에 대해서도 마찬가지로 남은 보석들 중 담을 수 있는 보석을 최대 힙에 삽입한다. 이때, 이전 가방에서 담은 보석들은 그대로 유지한다. 가방들은 최소 힙에 담겨있었기 때문에 이전 가방에서 담을 수 있는 보석들은 다음 가방에서도 담을 수 있다. 그렇기 때문에 가격 순으로 높은 가격의 보석들만 계속 가방에 담을 수 있게 된다.
🔡 코드
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())
jewells = []
bags = []
count = 0
for j in range(N):
heappush(jewells, list(map(int, input().rstrip().split())))
for b in range(K):
heappush(bags, int(input()))
can_steal = []
for _ in range(K):
bag = heappop(bags)
while jewells and jewells[0][0] <= bag:
heappush(can_steal, -heappop(jewells)[1])
if can_steal:
count += -heappop(can_steal)
elif not jewells:
break
print(count)해당 가방에 대해서 훔칠 수 있는 보석들(can_steal)이 존재하는 경우에만 카운트 하고, 보석들을 전부 담게 되었을 때의 예외처리 등을 적절히 수행해야 한다.
📚 고찰
그리디 알고리즘에서 힙이 효과적으로 사용될 수 있음을 알게해준 문제였다. 그리디 알고리즘의 특성상 정렬된 상태가 필요한데 정렬을 매번 수행하지 않고, 자료구조에 담을 때 부터 힙에서 반 정렬 상태를 유지함으로써 최대값, 최소값 등의 우선순위를 고려해 출력할 수 있기 때문에 시간적인 측면에서 이득을 볼 수 있다.
