[백준] 1202번. 보석 도둑(JAVA)

문제

https://www.acmicpc.net/problem/1202

---

풀이

import java.io.*;
import java.util.*;

public class Main{

    static long N, K;
    static PriorityQueue<Jewel> jewelQueue = new PriorityQueue<>((o1, o2) -> {
        if(o1.v != o2.v) {
            return Long.compare(o2.v, o1.v);  // 값 기준 내림차순
        }
        return Long.compare(o1.m, o2.m);  // 무게 기준 오름차순 (같을 때)
    });

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

        st = new StringTokenizer(br.readLine());

        N = Long.parseLong(st.nextToken());  // 보석 개수
        K = Long.parseLong(st.nextToken());  // 가방 개수

        // 보석 정보 입력
        List<Jewel> jewels = new ArrayList<>();
        for(long i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            long m = Long.parseLong(st.nextToken());  // 보석 무게
            long v = Long.parseLong(st.nextToken());  // 보석 가치
            jewels.add(new Jewel(m, v));
        }

        // 가방 정보 입력
        long[] bags = new long[(int) K];
        for(int i = 0; i < K; i++){
            bags[i] = Long.parseLong(br.readLine());
        }

        // 보석은 무게 오름차순으로 정렬 (같은 무게일 경우는 필요 없음)
        Collections.sort(jewels, Comparator.comparingLong(j -> j.m));
        // 가방은 무게 오름차순으로 정렬
        Arrays.sort(bags);

        long answer = 0;
        int jewelIndex = 0;

        // 각 가방에 대해 가능한 보석을 찾는다.
        for(int i = 0; i < K; i++) {
            long bagCapacity = bags[i];

            // 현재 가방에 들어갈 수 있는 모든 보석을 우선순위 큐에 넣는다.
            while (jewelIndex < N && jewels.get(jewelIndex).m <= bagCapacity) {
                jewelQueue.offer(jewels.get(jewelIndex));
                jewelIndex++;
            }

            // 우선순위 큐에서 가장 값이 높은 보석을 선택하여 가방에 넣는다.
            if (!jewelQueue.isEmpty()) {
                answer += jewelQueue.poll().v;  // 가장 높은 가치의 보석을 더한다.
            }
        }

        System.out.println(answer);
    }

    // 보석 클래스 정의
    private static class Jewel {
        long m;  // 무게
        long v;  // 가치

        public Jewel(long m, long v){
            this.m = m;
            this.v = v;
        }
    }
}

 

무게에 맞는 순으로 가방에 넣을 생각을 한다. 이 때 당연히 가치가 가장 큰 것을 위주로 넣어야 한다.

가방 무게는 계속 커지는데 왜 동일한 우선순위 큐를 사용하나?

어차피 우선순위큐는 무게 순으로 정렬되는 것이 아닌 가치의 순으로 정렬되기 때문에 당연히 그 가방에 들어갈 수 있는 모든 보석에 대하여 가치가 가장 높은 것이 들어가는 것이 맞기 때문이다.