[백준 - 1202] 보석 도둑 - Java

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

1202번: 보석 도둑

 

우선순위 큐를 활용한 그리디 문제이다.

 

Jewel은 무게와 가격 정보를 갖고있다. 맨 처음 입력받은 Jewel과 가방을 무게 오름차순으로 정렬한다.

들어갈 수 있는 무게가 작은 가방에 들어갈 수 있는 보석은 들어갈 수 있는 무게가 큰 가방에도 들어갈 수 있기 때문에 작은 가방에 넣는 것을 우선시한다.

 

 

우선순위 큐는 가방이 수용할 수 있는 무게의 보석을 넣고 가격 내림차순으로 정렬하여 갖고있는다.

그림에서 1번 가방에 들어갈 수 있는 보석을 다 넣었다면 1번 보석과 2번 보석이 들어가게 된다.

그 중에서 가격이 가장 비싼 보석을 꺼내온다면 2번 보석이 나오게 된다.

그 다음 2번 가방에 들어갈 수 있는 보석을 다 넣는 다면 1번 보석이 남아있었고, 3번 보석이 들어가게 된다.

그 중에서 가격이 가장 비싼 보석을 꺼내온다면 1번 보석이 나오게 된다.

가방을 모두 사용했기 때문에 탐색을 마친다.

 

public class Main {
    public static void main(String[] args) throws Exception{
        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());

        Jewel[] jw = new Jewel[N];
        int[] bags = new int[K];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            jw[i] = new Jewel(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

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

        // 가방 오름 차순 정렬
        Arrays.sort(bags);
        // 보석 무게 오름차순 정렬
        Arrays.sort(jw, new Comparator<Jewel>() {
            @Override
            public int compare(Jewel o1, Jewel o2) {
                return o1.weight-o2.weight;
            }
        });

        // 보석 가격이 높은 값 기준 힙
        PriorityQueue<Jewel> pq = new PriorityQueue<>();

        long result = 0;
        int p1 = 0, p2 = 0;

        // 1. 남은 가방 중 제일 작은 가방 선택 <-
        while(p1<K) {
            // 2. 선택된 가방에 넣을 수 있는 남은 보석 중 가장 비싼 보석을 선택 <- 힙 사용
            while(p2<N) {
                if(bags[p1]>=jw[p2].weight){
                    pq.offer(jw[p2]);
                    p2++;
                }
                else break;
            }
            if(!pq.isEmpty()) result += pq.poll().price;
            p1++;

        }
        System.out.println(result);
    }
}

class Jewel implements Comparable<Jewel>{
    int weight;
    int price;

    public Jewel(int weight, int price) {
        this.weight = weight;
        this.price = price;
    }

    @Override
    public String toString() {
        return "{" +
                "weight=" + weight +
                ", price=" + price +
                '}';
    }

    @Override
    public int compareTo(Jewel o) {
        return o.price-this.price;
    }
}