[백준 1202 JAVA] 보석도둑

 

우선순위 큐를 활용하는문제

 

1. 보석의 무게를 기준으로 오름차순 정렬하기 위해 priority queue를 생성해 보석의 무게와 가치를 넣어준다

2. 가방의 무게를 오름차순 정렬하기위해 priority queue를 생성해 넣어준다

3. 가치를 내림차순으로 넣어둘 priority queue를 넣어준다.

 

2번에서 생성한 가방의 무게 큐에서 하나를 뽑는다 (가장 적은 무게를 담을 수 있는 가방)

1번에서 생성한 보석들의 무게로 정렬되어있는큐에 가장 위에 요소와 가방이 담을수 있는 무게를 비교한다

가방이 담을수 있는 무게의 보석들을 전부 3번큐로 이동시킨다(가치만 전송하면 됨)

 

이렇게 되면 3번 큐에는 가방에 담을 수 있는 보석들만 있고, 가치가 높은 순으로 정렬되어 있다.

3번큐에 가장 위에잇는것을 뽑아 가방에 넣어주면된다.

 

계속해서 반복하면 3번큐에는 가방에 담을 수 있는 가장 높은 가치의 보석이 올라가있게 되어 답을 구할 수 있다.

 

주의 ) Priority queue가 빌 경우가 많이 생기니 꼭 예외처리를 해야한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


class Jewelry{
    int weight;
    int value;

    public Jewelry(int w, int v) {
        this.weight = w;
        this.value = v;
    }
}

class Main {
    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> jewl = new PriorityQueue<>(new Comparator<Jewelry>() {
            @Override
            public int compare(Jewelry o1, Jewelry o2) {
                if (o1.weight == o2.weight) {
                    return o2.value - o1.value;
                }
                return o1.weight - o2.weight;
            }
        });
        PriorityQueue<Integer> bag = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            jewl.add(new Jewelry(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        for (int i = 0; i < K; i++) {
            int k = Integer.parseInt(br.readLine());
            bag.offer(k);
        }
        long answer = 0;

        PriorityQueue<Integer> valueq = new PriorityQueue<>(Comparator.reverseOrder());
        while(!bag.isEmpty()){
            int bagpeek = bag.poll();
            while(!jewl.isEmpty() && jewl.peek().weight<=bagpeek){
                valueq.add(jewl.poll().value);
            }
            if(!valueq.isEmpty()){
                answer += valueq.poll();
            }
        }
        System.out.println(answer);
    }
}