[BOJ] Q1202 보석 도둑

[BOJ] Q1202 보석 도둑

Question

Language: Python

Difficulty: Gold 2

해당 문제는 우선순위 큐를 활용해서 풀이를 진행해야한다.

우선, 보석 무게, 가치에 대한 최소힙을 통해 가지고 있는 상태로 진행하여야한다.

그런 다음, 각각의 가방에 대해서 탐색을 진행해야되는데, 이때 가방이 가지는 무게(수용량)보다 작은 보석에 대해서 또다른 힙을 통해 관리를 해야한다. 이때 힙을 구성할 때는 보석의 가치가 큰 순서대로 관리될 수 있도록 최대힙으로 구성한다.

해당 가방의 수용량보다 작은 보석을 모두 찾은 이후에는 찾은 보석들(최대힙)에서 가장 가치가 큰 보석을 꺼내서 이를 가방에 저장하게 된다.

보석을 무게에 대해서 저장 할때는 최소힙으로 관리하게 되고, 그 중에서 다시 가치에 대해서 따질 때는 최대힙을 활용하게 된다.

Solution

from heapq import heappush,heappop
def solution():
    bags.sort()
    result=0
    candidates=[]
    for bag_weight in bags:
        while jewerly and bag_weight >= jewerly[0][0]:
            weight,priority=heappop(jewerly)
            heappush(candidates,(-priority))
        
        if candidates:
            result-=heappop(candidates)

    return result


if __name__== "__main__":
    N,K=map(int,input().split())
    jewerly=[]
    bags=[]
    
    for _ in range(N):
        weight,priority=map(int,input().split())
        heappush(jewerly,(weight,priority))
        
    bags=[int(input()) for _ in range(K)]
    
    print(solution())

아니면 아래와 같은 풀이도 가능하다. 가방과 보석을 같은 리스트에 저장하게 되는데, 이때 가방의 가치는 -1로 해서 저장한다. 그런 뒤, 무게는 오름차순, 가치는 내림차순으로 해서 정렬을 수행한다.

그렇게 한 뒤에, 해당 리스트에 순회를 진행하게 되면서 가치가 -1이 아닌경우(즉, 보석인 경우) 최대힙에 보석의 가치를 저장하도록 한다.

그리고 만약 가치가 -1인 경우(가방인 경우) 최대힙이 존재하는 경우(찾은 보석이 있는 경우) 해당 보석 중에서 최대값을 가방에 저장하도록 한다.

사실, 위의 풀이와 본질적으로 동일한 풀이이다.

Solution 2

import heapq
def solution():    
    jewerly_bags.sort(key=lambda x : (x[0],-x[1]))

    heap=[]

    result=0
    for weight,priority in jewerly_bags:
        if priority != -1:
            heapq.heappush(heap,(-priority))
        else:
            if heap:
                result-=(heapq.heappop(heap))

    return result


if __name__== "__main__":
    N,K=map(int,input().split())
    jewerly_bags=[]
    bags=[]
    for _ in range(N):
        weight,priority=map(int,input().split())
        jewerly_bags.append((weight,priority))
    for _ in range(K): 
        jewerly_bags.append((int(input()),-1))
    
    print(solution())