[Baekjoon 1202] 보석도둑

문제

💛Ⅱ [Baekjoon 1202 - 보석도둑]

문제 풀이 방법

처음에는 보석을 가격 순으로 내림차순 정렬하고 가방을 무게 순으로 오름차순 정렬한 후, 무게 가장 작은 가방부터 for문을 돌면서 가장 비싼 보석을 가방에 들어갈 수 있는지 확인하였다. 하지만 시간초과가 발생하였고, 더 효율적인 알고리즘을 생각해야 했다.

1. 보석을 무게 순으로 오름차순 정렬한다.
2. 가방을 무게 순으로 오름차순 정렬한다.
3. 가장 무게가 작은 가방부터 가장 싼 보석부터 담을 수 있을 때까지 담는다.
   1. 이때 가방 배열은 보석의 가격을 기준으로 한 우선순위 큐를 사용한다.
   2. 보석을 담을 수 없다면, 담은 보석 중에 가장 비싼 보석만 남긴다.

풀이 코드

Python → 시간초과!!

import sys
from collections import deque
input = sys.stdin.readline

N, K = map(int, input().split())
jewelry = [list(map(int, input().split())) for _ in range(N)]
bag = [int(input()) for _ in range(K)]
weight = [0]*K

jewelry.sort(key=lambda x:x[1], reverse=True) # 가격 순으로 내림차순 정렬
bag.sort() # 무게 순으로 오름차순

# 가장 무게가 작은 가방부터 가장 비싼 보석을 담도록 한다.
for idx,b in enumerate(bag):
    for idx2,j in enumerate(jewelry):
        if j[0] <= b: # 현재 가방에 들어갈 수 있는지
            weight[idx] = j[1]
            jewelry.remove(j)
            break

print(sum(weight))

Python

import sys
import heapq
input = sys.stdin.readline

N, K = map(int, input().split())
jewelry = [list(map(int, input().split())) for _ in range(N)]
bag = [int(input()) for _ in range(K)]
answer = 0

jewelry.sort(key=lambda x:x[0]) # 무게 순으로 오름차순 정렬
bag.sort() # 무게 순으로 오름차순

# 가장 무게가 작은 가방부터 가장 비싼 보석을 담도록 한다.
q = []
idx = 0
for b in bag:
    while idx<N and jewelry[idx][0] <= b: # 담을 수 있을 때까지 담고
        heapq.heappush(q, -jewelry[idx][1])
        idx+=1
    if q:
        answer += -(heapq.heappop(q)) # 그 중 가장 비싼 것만 저장
print(answer)