가치가 큰 보석을 최대한 크기가 작은 가방에 넣어줌 (가치가 큰 보석을 크기가 작은 가방부터 순회하며 넣을 수 있다면 넣고 방문처리)
가방이 다 찼다면 최대 보석가치를 가져온 것임
입력 후 정렬 상태
이 풀이 방식으로는 시간초과를 피할 수 없었다. 문제 해결을 위해 다른 블로그와 유튜브를 찾아보다 우선순위 큐라는 개념을 학습했다.
- 입출력 예시
- 틀린 코드
import sys
imput = sys.stdin.readline
n, k = map(int, input().split())
# 보석과 가방 입력
jem = [list(map(int, input().split())) for _ in range(n)]
bag = [int(input()) for _ in range(k)]
# 보석을 무게순으로 정렬한 후 가치가 높은순으로 다시정렬
jem = sorted(jem, key=lambda x:x[0])
jem = sorted(jem, key=lambda x:x[1], reverse=True)
# 가방은 크기가 작은거부터 정렬
bag = sorted(bag)
pack = [False] # 가방을 사용했는지 체크
ans, cnt = 0, 0 # 보석의 가치, 사용한 가방 개수
for i in range(len(jem)):
for j in range(len(bag)):
# 정렬된 보석을 돌면서 작은 가방부터 확인
# 가방이 비어있고, 보석이 가방에 들어갈 수 있는 크기라면
if jem[i][0] <= bag[j] and pack[j] == False:
pack[j] == True # 가방 사용했다고 체크
ans += jem[i][1] # 보석 가치 더해줌
cnt += 1 # 가방 사용개수 +1
break
# 가방을 전부 사용했다면 반복종료
if cnt == len(bag):
print(ans)
break
- 우선순위 큐
FIFO 구조인 일반적인 큐와 달리 데이터에 우선순위를 부여해 들어간 순서에 상관없이 우선 순위가 높은 데이터가 먼저 나오는 구조이다.
힙(Heap)이라는 완전이진트리 자료구조를 가지고 구현한다.
- 문제풀이
보석과 가방을 무게, 크기기준 오름차순 정렬
가방의 길이만큼 반복하며 현재 가방에 들어갈 수 있는 만큼만 최대 힙을 이용해 우선순위 큐에 저장
반복 1회가 끝나면 우선순위 큐에서 가장 우선순위가 높은 보석을 꺼냄
보석, 가방 정렬
1번째 가방 반복, 2번째 가방 반복
보석 리스트에서 현재 가방에 들어갈 수 있는 보석들을 보석 크기순으로 우선순위를 부여해 우선순위 큐에 넣은 상태
- 코드
import sys
import heapq
input = sys.stdin.readline
n,k = map(int,input().split())
gem = [list(map(int,input().split())) for _ in range(n)]
bag = [int(input()) for _ in range(k)]
gem.sort() # 보석을 무게순 정렬
bag.sort() # 가방 크기순 정렬
Q =[] # 우선순위 큐가 될 리스트
answer = 0
# 가방 작은 순부터 반복
for i in bag:
# 보석의 무게가 가방에 들어갈수 없을때까지 반복
while gem and gem[0][0]<=i:
# 최대힙을 이용해서 우선순위 큐에 추가
heapq.heappush(Q, -heapq.heappop(gem)[1])
# 반복이 끝난 후 가장 큐의 앞에있는 값을 pop하여 더해줌
if Q: answer -= heapq.heappop(Q)
print(answer)