[Algorithm] 1202. 보석도둑

www.acmicpc.net/problem/1202

1202번: 보석 도둑

우선순위 큐 + 그리디

1. 보석을 무게기준으로 정렬한다.(오름차순)
2. 가방 정렬(오름차순)
3. 가방 수 만큼 반복하면서 보석을 우선순위 큐에 담는다. (value값 내림차순 정렬)
4. 보석무게가 가방제한보다 커지면 가방 인덱스 증가.
5. 다음 가방시행 전에 우선순위 큐에서 하나 뽑아서 value 누적

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

//129936KB , 1276ms
public class Main {

    static class Jewelry {
        int mess;
        int value;

        public Jewelry(int mess, int value) {
            this.mess = mess;
            this.value = value;
        }

        public int getMess() {
            return mess;
        }

        public int getValue() {
            return value;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        PriorityQueue<Jewelry> jewelries = new PriorityQueue<>((a, b) -> a.getMess() - b.getMess()); // get 메소드를 이용한 정렬
        int[] bag = new int[K];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int mess = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            jewelries.add(new Jewelry(mess, value));
        }
        for (int i = 0; i < K; i++) {
            bag[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(bag);

        int idx = 0;
        long answer = 0L;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int limit : bag) {
            while (!jewelries.isEmpty() && jewelries.peek().getMess() <= limit) {
                pq.add(jewelries.poll().getValue());
                if (jewelries.isEmpty()) break;
            }
            if (!pq.isEmpty()) {
                answer += (long) pq.poll();
            }
        }
        System.out.println(answer);
    }
}

• 람다식을 이용해 우선순위 큐를 정렬.