[백준] 보석 도둑 - 1202

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다.
상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

풀이

우선순위 큐를 사용하여 풀었다.

보석의 정보(무게, 가격)를 저장하는 클래스 Jewel을 정의하고,
무게를 오름차순 기준으로 우선순위 큐(weight)를 생성해, 보석들을 저장한다.
가격을 내림차순 기준으로 우선순위 큐(price)를 생성한다.

오름차순으로 정렬된 가방을 순회하며 아래를 반복한다.
1. 가방의 무게보다 작거나 같은 우선순위 큐(weight)의 보석들을 추출한다.
2. 추출한 보석들을 우선순위 큐(price)에 저장한다.
3. 우선순위 큐(price)가 비어있지 않은 경우 우선순위가 가장 높은 보석을 추출하며, 보석의 가격을 answer에 저장한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // input | N & K -> int
        String[] NK = br.readLine().split(" ");
        int N = Integer.parseInt(NK[0]);
        int K = Integer.parseInt(NK[1]);

        // init | weight & price -> priorityQueue
        PriorityQueue<Jewel> jewels_weight = new PriorityQueue<>((j1, j2)->{
            return j1.weight-j2.weight; // 무게기준 오름차순
        });

        PriorityQueue<Jewel> jewels_price = new PriorityQueue<>((j1, j2)->{
            return j2.price-j1.price;   // 가격기준 내림차순
        });

        // input | M & V -> jewels_weight -> priorityQueue
        for(int i=0; i<N; i++){
            String[] MV = br.readLine().split(" ");

            int weight = Integer.parseInt(MV[0]);
            int price = Integer.parseInt(MV[1]);

            jewels_weight.offer(new Jewel(weight, price));
        }

        // input & sort | weights -> int[] -> 가방의 무게를 입력 받고 오름차순 정렬
        int[] weights = new int[K];
        for(int i=0; i<K; i++)
            weights[i] = Integer.parseInt(br.readLine());

        Arrays.sort(weights);
        
        // solve | [가방의 무게보다 작은 jewels_weight의 노드를 뽑아
        // jewels_price에 offer -> 가장 높은(비싼) 보석의 가격을 answer에 저장 후 poll] -> 반복
        Long answer = 0L;
        for(int weight: weights){
            while(!jewels_weight.isEmpty()){
                if(weight < jewels_weight.peek().weight){
                    break;
                } else{
                    jewels_price.offer(jewels_weight.poll());
                }
            }
            
            if(!jewels_price.isEmpty())
                answer += jewels_price.poll().price;
        }

        // print |
        System.out.println(answer);
    }   

    static class Jewel{
        int weight;
        int price;

        Jewel(int w, int p){
            weight = w;
            price = p;
        }
    }
}