boj 1202 보석도둑(그리디, 우선순위 큐) Java

문제

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

상덕이가 털 보석점에는 보석이 총 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)

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

출력

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

예제 입력 1

2 1
5 10
100 100
11

예제 출력 1

10

예제 입력 2

3 2
1 65
5 23
2 99
10
2

예제 출력 2

164

나동빈님이 알고리즘 공부법을 봤는데 그리디, bfs등 기본기를 많이 하라고 해서 그리디를 줘패고 있는중!

작동방식

입력으로부터 보석의 개수와 가방의 개수를 받습니다.
각 보석의 무게와 가치를 입력으로 받습니다.
입력으로부터 각 가방이 담을 수 있는 최대 무게를 받습니다.
보석들을 무게에 따라 오름차순으로 정렬합니다.
가방들도 무게에 따라 오름차순으로 정렬합니다.
각 가방에 대해, 가방이 담을 수 있는 무게 이하의 보석 중 가장 가치가 높은 보석을 선택합니다.
선택한 보석의 가치를 합산하여 결과를 출력합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    // 보석 클래스 정의. 보석은 무게와 가치를 가집니다.
    static class Jewel implements Comparable<Jewel> {
        int weight;
        int price;

        public Jewel(int weight, int price) {
            this.weight = weight;
            this.price = price;
        }

        // 비교 메서드를 오버라이드하여 보석을 가격에 따라 정렬합니다.
        @Override
        public int compareTo(Jewel o) {
            return o.price - this.price; 
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 보석의 개수(N)와 가방의 개수(K)를 입력 받습니다.
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        // 보석 정보를 입력 받아 리스트에 저장합니다.
        List<Jewel> jewels = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            jewels.add(new Jewel(weight, price));
        }

        // 보석 리스트를 무게에 따라 오름차순으로 정렬합니다.
        jewels.sort(Comparator.comparingInt(j -> j.weight));

        // 가방 정보를 입력 받아 배열에 저장합니다.
        int[] bags = new int[K];
        for (int i = 0; i < K; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }

        // 가방 배열을 무게에 따라 오름차순으로 정렬합니다.
        Arrays.sort(bags);

        // 우선순위 큐를 이용하여 가장 가치 높은 보석을 먼저 추출합니다.
        PriorityQueue<Jewel> pq = new PriorityQueue<>();
        long result = 0;
        int index = 0;

        // 각 가방에 대해 가능한 가장 가치 높은 보석을 찾아 결과에 더합니다.
        for (int i = 0; i < K; i++) {
            while (index < N && jewels.get(index).weight <= bags[i]) {
                pq.offer(jewels.get(index++));
            }
            if (!pq.isEmpty()) {
                result += pq.poll().price;
            }
        }

        // 최종 결과를 출력합니다.
        System.out.println(result);
    }
}