백준 Java | BOJ 1202 보석 도둑

package DAY03.P1202;

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

class Diamond {
    int weight;
    int price;
    int id;
    Diamond(int weight, int price, int id){
        this.weight = weight;
        this.price = price;
        this.id = id;
    }
    @Override
    public String toString(){
        return "(" + weight + ", " + price + ")";
    }
}
public class Main {
    public static int N;
    public static int K;
    public static ArrayList<Diamond> candidate;
    public static ArrayList<Integer> bag;
    public static int[] visited;
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/DAY03/P1202/input.txt"));
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        candidate = new ArrayList<>();
        bag = new ArrayList<>();

        String[] input = bf.readLine().split(" ");
        N = Integer.parseInt(input[0]);

        visited = new int[N];
        K = Integer.parseInt(input[1]);
        for (int i=0;i<N;i++){
            input = bf.readLine().split(" ");
            candidate.add(new Diamond(Integer.parseInt(input[0]), Integer.parseInt(input[1]), i));
        }
        for (int i=0;i<K;i++){
            bag.add(Integer.parseInt(bf.readLine()));
        }

        candidate.sort(new Comparator<Diamond>() {
            @Override
            public int compare(Diamond o1, Diamond o2) {
                return o1.weight - o2.weight;
            }
        });
        Collections.sort(bag);

        PriorityQueue<Diamond> priority_queue = new PriorityQueue<>(new Comparator<Diamond>() {
            @Override
            public int compare(Diamond o1, Diamond o2) {
                return o2.price - o1.price;
            }
        });

        long profit = 0;
        int diamond_index = 0;
        boolean[] queue_contains = new boolean[N];
        for (Integer capability : bag){
            for (;diamond_index<N;diamond_index++){
                Diamond diamond = candidate.get(diamond_index);
                if (capability >= diamond.weight){
                    if (!queue_contains[diamond.id] && visited[diamond.id] != 1){
                        queue_contains[diamond.id] = true;
                        priority_queue.offer(diamond);
                    }
                } else {
                    break;
                }
            }
            // 가장 비싼 걸 pop
            if (priority_queue.size() != 0){
                Diamond current = priority_queue.poll();
                visited[current.id] = 1;
                queue_contains[current.id] = false;
                profit += current.price;
            }
        }
        System.out.println(profit);
    }
}