[백준] 1202 : 보석도둑 (Priority Queue 우선순위 큐) - JAVA

백준 알고리즘 분류 (그리디 알고리즘)

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

1202번: 보석 도둑

 

# 문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

 

# 예제

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000) 모든 숫자는 양의 정수이다.

2 1
5 10
100 100
11

 

출력

10

 

# 필요개념

그리디 알고리즘의 특성상 가장 비싼 보석을 담아야한다. 그러기 위해서는 생각할 것이 몇 가지 있다.

1. 가방에 넣을 수 있는 무게가 적은 가방은 넣을 수 있는 무게가 큰 가방보다 제한사항이 많다. 보석이 무겁다고 비싼 게 아니기 때문에, 선택권은 무게가 작은 가방에게 먼저 주는게 좋다. -> 가방을 배열에 담아 오름차순 정렬한다.
2. 가방이 보석보다 많을 수 있다. -> 우선순위 큐를 이용할 것이기 때문에 isEmpty를 확인해야 한다.

무게를 기준으로 오름차순 정렬하고, 무게가 같다면 가격을 기준으로 내림차순 한다. 이렇게 해서 가방의 최대 무게와 비교 후, 최대 무게보다 작으면 우선순위 큐에 넣어준다. 이때 우선순위큐는 내용물을 내림차순 정렬 하도록 생성한다.

 

다 넣었으면 우선순위 큐는 자동으로 내림차순 정렬을 해줄 것이다. 그럼 나는 맨 앞의 원소를 넣어주면 된다! 

 

✅ 우선순위 큐

 

 📌우선순위 큐?

 

PriorityQueue (우선순위 큐)는 일반적인 큐처럼 들어온 순서대로 데이터가 나가는 것(FIFO)이 아닌, 우선순위를 먼저 결정해 우선순위가 높은 데이터가 먼저 나가도록 하는 자료구조이다.

 

우선순위 큐를 만들 때, Comparable의 compareTo 메소드를 이용해 우선순위 조건을 리턴해준다. 관련 내용은 아래를 참고하면 된다.

https://wanna-developer02.tistory.com/79

[백준] 11650 : 좌표 정렬하기 (Comparator<int[]> 이차원배열 정렬) - JAVA

 

우선순위 큐는 보통 Heap을 이용해 구현되어있다. 그래서 O(NlongN)의 시간복잡도를 갖는다.

 

 

 📌우선순위 큐 메소드

메소드	설명
add(e)	원소를 추가하고, 큐가 이미 꽉 찬 경우 예외 발생시킴. (IllegalStateException)
offer(e)	원소를 추가하고, 큐가 이미 꽉 찬 경우 false 리턴
remove()	원소를 삭제하고, 큐가 비어있는 경우 예외 발생시킴.
poll()	원소를 삭제하고, 큐가 비어있는 경우 null 리턴
element()	첫 번째 값을 반환하고  삭제는 하지 않으며 , 큐가 비어있는 경우 예외 발생시킴
peek()	첫 번째 값을 반환하고 삭제는 하지 않으며, 큐가 비어있는 경우 null 리턴
clear()	큐를 초기화시킴

 

# Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public 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());
        List<Jw> lst = new ArrayList<>();

        for (int i = 0 ; i < n ; i++) {
            st = new StringTokenizer(br.readLine());
            Jw j = new Jw();
            j.weight = Integer.parseInt(st.nextToken());
            j.price = Integer.parseInt(st.nextToken());
            lst.add(j);
        }

        // w,p
        Collections.sort(lst, new Comparator<Jw>() {
            @Override
            public int compare(Jw o1, Jw o2) {
                if (o1.weight == o2.weight) return o2.price - o1.price;
                return o1.weight - o2.weight;
            }
        });
        long sol = 0;
        int[] bags = new int[k];
        for (int i = 0 ; i < k ; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(bags);

        int idx = 0;
        PriorityQueue<Integer> p = new PriorityQueue<>(Comparator.reverseOrder());
        for (int i = 0 ; i < k ; i++) {
            while (idx < n && lst.get(idx).weight <= bags[i]) {
                p.offer(lst.get(idx).price);
                idx++;
            }
            if (!p.isEmpty()) sol += p.poll();
        }
        System.out.println(sol);
    }

    static class Jw {
        int weight;
        int price;
        public void Jw(int w, int p) {
            this.weight = w;
            this.price = p;
        }
    }
}

 

보석의 무게와 가격을 담은 객체인 Jw를 따로 생성하여 다뤘음.

 

# 결과