백준 1202번 : 보석도둑 [자바]

 

🧫 문제 분석

✔️ 출처

보석 도둑 골드 2

 

📖 문제

 

우선순위 큐 문제

 

주어진 가방을 무게 기준 오름차순 정렬하여 

가장 작은 가방부터 보석을 담는다.

 

가장 작은 가방이 담을 수 있는 보석들 중 최대 값어치인 보석을 해당 가방에 담는식으로 하면 된다.

 

우선순위 큐를 가격이 높은순으로 사용한다.

현재 선택한 가방이 담을 수 있는 보석들을 우선순위 큐에 다 담고

하나를 꺼낸다. 이때 꺼낸 보석이 현재 가방이 담을 수 있는 

최대 가격의 보석이 된다. 

 

그리고 정답 범위가 30만 * 100만이기에 long타입으로 가격을 계산해야한다.

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {

    static class Gem {
        int m, v;

        public Gem(int m, int v) {
            this.m = m;
            this.v = v;
        }

    }
    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());

        Gem[] gems = new Gem[N];
        int[] back = new int[K];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            gems[i] = new Gem(m, v);
        }

        for (int i = 0; i < K; i++) {
            back[i] = Integer.parseInt(br.readLine());
        }

        // 무게 오름차순으로 정렬
        Arrays.sort(gems, (o1, o2) -> o1.m - o2.m);
        // 가방도 오름차순으로 정렬
        Arrays.sort(back);

        // 가격 내림차순으로 정렬
        PriorityQueue<Gem> pq = new PriorityQueue<>((o1, o2) -> o2.v - o1.v);

        int idx = 0;
        long answer = 0;
        for (int i = 0; i < K; i++) {
            // 해당 가방 무게로 담을 수 있는 모든 보석을 우선순위 큐에 담는다.
            while (idx < N && back[i] >= gems[idx].m) {
                pq.add(gems[idx]);
                idx++;
            }

            // 꺼낸 보석은 해당 가방 무게로 담을 수 있으면서 최대 가격을 갖는 보석이다.
            if (!pq.isEmpty()) {
                Gem target = pq.poll();
                answer += target.v;
            }
        }

        System.out.println(answer);

    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.