https://www.acmicpc.net/problem/1202
문제
요약하자면, 첫줄에 N(보석 개수)와 K(가방 개수)가 주어지고,
다음에 N줄에 걸쳐 보석의 무게와 보석의 가격이 주어지며, 다음 K줄에 걸쳐 각 가방의 허용 무게가 주어집니다. 상덕이가 K개의 가방에 대해 각각 허용 무게를 지키며 보석을 훔칠 때, 최대 가격을 구하는 문제입니다.
여기서 한 가방에는 하나의 보석만 넣을수 있다❗️
문제 풀이
- 처음 문제 접근
처음에 문제를 풀땐, heapq를 생각 못하고 deque()를 선언해서 가방을 오름차순으로 정렬하고, 보석을 내림차순으로 정렬하여 popleft()해주는 식으로 접근 했습니다
이렇게 접근해서 , 문제에서 주어진 예시들은 통과했고, 다른 분들이 반례를 주신 예시들도 다 통과했는데 자꾸 런타임에러(IndexError)가 발생했습니다...
런타임에러(IndexError)가 발생한 이유는 아직 정확히 파악을 못했지만, 해당 문제에서는 deque()모듈을 지원하지 않는다고 해서 이것 때문인것 같습니다.
런타임에러(IndexError) 풀이
import sys
input=sys.stdin.readline
from collections import deque
n,k =map(int, input().split())
a=[]
bag=[]
for i in range(n):
x,y=map(int, input().split())
a.append((x,y))
if k!=0:
for j in range(k):
tmp=int(input())
bag.append(tmp)
bag.sort()
a.sort(key=lambda x:x[1], reverse=True)
a=deque(a)
bag=deque(bag)
cnt=0
res=0
while bag:
temp=bag.popleft()
if cnt==k:
break
else:
for i in range(n):
if temp>= a[i][0]:
res+=a[i][1]
a.popleft()
break
cnt+=1
print(res)
else:
print(0)- 정답 풀이
보석의 무게, 가격 리스트와 가방의 무게 리스트를 오름차순으로 정렬하고, 각 가방별로 훔칠 수 있는 보석을 최대힙을 통해 탐색하는게 핵심입니다.힙에 대해 궁금하시다면
👉클릭
정답 풀이 코드
import sys
import heapq
input=sys.stdin.readline
n,k = map(int,input().split())
gem = [[*map(int,input().split())] for _ in range(n)]
bag = [int(input()) for _ in range(k)]
gem.sort();bag.sort()
result = 0;tmp = []
for bag in bag:
while gem and gem[0][0] <= bag:
heapq.heappush(tmp, -gem[0][1])
heapq.heappop(gem)
if tmp:
result -= heapq.heappop(tmp)
print(result)
총 n개의 보석, k개의 가방을 입력받습니다. gem에는 [ [ 보석무게, 보석가격], …] 형태의 2중 리스트가 생성됩니다. bag에는 k개 가방에 대해 허용 무게가 저장됩니다.
gem를 보석 무게에 대해 오름차순, 보석 무게가 같을땐 가격으로 오름차순 정렬하고, bag도 오름차순 정렬합니다. result는 k개의 가방으로 훔칠 수 있는 보석 가격의 최대값이 저장될 변수이고, 0으로 초기화 합니다. tmp는 최대 힙입니다. 가방의 무게가 작은 것부터, 해당 가방으로 훔칠 수 있는 최대 보석의 가격을 탐색하는 역할을 합니다.
for 문으로 bag에서 가방의 무게를 작은 것 부터 반복합니다. 각 가방의 무게에 대해, 그 가방으로 훔칠 수 있는 보석들을 while문을 돌며 최대 힙에 저장합니다. while 문은 gems 보석 리스트가 비어있지 않고, gems에서 제일 가벼운 보석의 무게가 bag 이하이면, tmp에 마이너스를 취해서 보석의 가격을 삽입(heappush)하고, 그 보석은 gems에서 heappop 합니다. - 를 취해서 heap에 삽입하는 이유는 보석의 무게는 0 이상인데 음수로 최소힙에 저장하면, 최소값은 음수로 제일 작은 수 이고, 이는 다시 -를 취해주면 양수로 최대값이기 때문입니다. 즉, -를 취해서 최소힙을 최대힙으로 사용하는 것 입니다.
tmp가 존재하는 경우. 즉, 현재 bag 무게 이하의 훔칠 보석이 있다면, heappop으로 최대 가격의 보석을 빼서 result에 갱신합니다. 이 때, result -= heapq.heappop(tmp)를 하는 이유는 현재 힙에 보석의 가격이 음수로 저장되있기 때문입니다.
