[python] baekjoon 1202 보석 도둑

문제

-> 문제 링크 : https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

문제풀이

가방의 개수와 보석의 개수 모두 30만으로 O(logN) 이하의 시간 복잡도로 문제를 해결해야 한다.

가방에 들어가는 보석을 선택하는 문제이든 보석을 담을 수 있는 가방을 선택하는 문제이든 시간이 O(logN)으로 찾을 수 있어야 문제를 해결할 수 있다.

 

기준을 가방으로 잡고, 현재 가방에 들어갈 수 있는 보석 중 가장 비싼 보석을 넣는 방식으로 문제를 해결할 수 있다.

가방과 보석을 모두 오름차순으로 정렬한 뒤 가장 작은 무게를 가진 가방과 보석부터 비교해나간다. 

보석과 가방의 맨 처음을 가리키는 두 개의 인덱스를 만들고 두 인덱스에 해당하는 값을 비교해나가면서 인덱스를 움직인다.

만약 가방이 더 크다면 현재 보석 이후에 있는 보석을 담을 수 있는 가능성이 있으므로 보석을 가리키는 인덱스를 증가시킨다.

보석이 더 크다면 현재 가방은 이 보석보다 뒤에 있는 보석은 담을 수 없으므로 현재까지 나온 보석들 중 가장 값비싼 보석을 선택한다.

이 과정을 반복하다 보면 항상 가방에는 담을 수 있는 보석 중 가장 비싼 보석만이 담아지게 된다.

값비싼 보석을 추가하고 삭제하는 연산을 O(logN)에 해결해야 하므로 힙을 사용해야 한다.

 

 

코드

import sys
import heapq

N, K = map(int, sys.stdin.readline().rstrip().split(" "))

jewerly = []
for _ in range(N) :
    M, V = map(int, sys.stdin.readline().rstrip().split(" "))
    jewerly.append((M,V))

bags = []
for _ in range(K) :
    bags.append(int(sys.stdin.readline().rstrip()))

remains = []

bags = sorted(bags)
jewerly = sorted(jewerly)

maxHeap = []

b_i = 0
j_i = 0
answer = 0
while b_i < K and j_i < N:

    if bags[b_i] >= jewerly[j_i][0] :
        weight, value = jewerly[j_i]
        heapq.heappush(maxHeap, -value)
        j_i += 1

    elif bags[b_i] < jewerly[j_i][0] :

        if maxHeap :
            maxValue = heapq.heappop(maxHeap)
            answer += -maxValue
        b_i += 1


while b_i < K and maxHeap:
    maxValue = heapq.heappop(maxHeap)
    answer += -maxValue
    b_i += 1

print(answer)

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.