[BOJ] 1202 보석도둑 - Java

✨ 우선순위 큐 & 정렬

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

1202번: 보석 도둑

---

📍 고려해야할 점

• 훔칠 수 있는 보석 가격의 최대의 합을 구해야 한다. 
• 보석의 개수 <= 30만
• 가방의 개수 <= 30만
• 가방에 담을 수 있는 무게 <= 1억
• 보석의 무게 <= 100만

 

 

🕹️ 풀이 방법 

처음에는 보석 가격의 최대 합을 구해야하기 때문에 보석의 가격이 내림차순으로 저장되도록 우선순위 큐에 넣어서 구하면 될 것이라 생각했었다.

그러나 이 방법으로 진행하면 가방이 보석의 무게를 담을 수 있는지 알 수 없게 되고(무게는 고려하지 않고 가격의 값 순서대로 저장했기 때문)

모든 가방을 하나씩 비교하여 가방에 담을 수 있는지 확인하는 방법밖에 떠오르지 않았다. 👉 이 방법은 가방의 개수와 보석의 개수가 최대 30만 개이므로 시간 초과가 발생할 것이다. 

 

 

---

 

그래서 다시 생각해보았다.

보석의 무게가 오름차순으로 저장되도록 하고 가방 또한 오름차순으로 정렬한다.

가방에 담을 수 있는 보석 중에 최대 가격의 보석을 total 값에 더해주면 되는데, 이 때 보석의 가격을 내림차순으로 저장되도록 하는 우선순위 큐를 사용하면 된다. 

 

코드로 한 번 구현해보자. 

long total=0;

PriorityQueue<Integer> jPrice = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순으로 정렬

for(int i=0; i<K; i++){
    while (!jewelry.isEmpty() && jewelry.peek().m <= bags[i]) {
        jPrice.add(jewelry.poll().v);
    }
    if(!jPrice.isEmpty()) total+=jPrice.poll();
}

 

jewerly는 보석의 무게가 내림차순으로 (만약 무게가 같다면 가격이 오름차순) 정렬되어있는 우선순위 큐이다.

1. K는 가방의 개수로 현재 가방에 담을 수 있는 보석들을 while문을 돌며 탐색한다.
2. 담을 수 있다면 jPrice 우선순위큐에 넣어 가격이 내림차순으로 정렬되게끔 하고, 만약 보석이 비어있거나 보석의 무게를 가방에 담을 수 없다면 while문을 빠져나온다.
3. 현재 가방에 담을 수 있는 보석 중 가장 가격이 높은 것 (우선순위 큐에 제일 앞에 있는 것 뽑아내기) 을 total에 더한다. 

 

보석의 최대 무게는 100만이고, 개수는 30만 개이므로 보석의 합(total)은 long 타입으로 선언해야 한다. 

 

 

 

 

 

 

👩‍💻 전체 코드 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class BOJ_1202_보석도둑 {

    static class Info implements Comparable<Info>{
        int m, v;

        public Info(int m, int v){
            this.m=m;
            this.v=v;
        }
        @Override
        public int compareTo(Info o){
            if(m==o.m) return o.v-v;
            else return m-o.m;
        }
    }

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

        int N = Integer.parseInt(st.nextToken()); // 보석 개수
        int K = Integer.parseInt(st.nextToken()); // 가방 개수

        PriorityQueue<Info> jewelry = new PriorityQueue<>();
        int[] bags = 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());

            jewelry.add(new Info(m, v)); // 보석의 무게가 낮은 순서대로 저장 (오름차순) -> 무게가 같다면 가격이 높은 순서대로 저장(내림차순)
        }

        for(int i=0; i<K; i++){
            st = new StringTokenizer(br.readLine());

            bags[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(bags); // 가방은 담을 수 있는 최대 무게가 낮은 순서대로 저장 (오름차순)

        long total=0;

        PriorityQueue<Integer> jPrice = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순으로 정렬

        for(int i=0; i<K; i++){
            while (!jewelry.isEmpty() && jewelry.peek().m <= bags[i]) {
                jPrice.add(jewelry.poll().v);
            }
            if(!jPrice.isEmpty()) total+=jPrice.poll();
        }

        bw.write(total + " ");
        bw.flush();
        bw.close();
    }
}