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

---

문제는 대략 이렇고, 제가 지금 시간이 없어서 대략 어떻게 풀었는지만 간단히 쓰자면

 

우선 보석의 정보를 2차원 배열로 입력받고, 무게를 기준으로 오름차순 정리한다.
그리고 가방의 수용량을 배열로 입력받고 오름차순 정리한다.

 

가방 수용량이 담긴 배열을 처음부터 돌면서, 해당 가방이 담을 수 있는 수용량까지의 무게를 가진 모든 보석들의 가치를 (높은 값이 우선인)우선순위 큐에 담는다. 다 담았으면 그 우선순위 큐에서 poll()해서 나오는 값이 해당 수용량에서 가질 수 있는 최고 가치의 보석이므로 sum에 더해 주며, 이 과정을 가방 개수만큼 반복한다.

import java.lang.StringBuilder;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.PriorityQueue;

public class JewelryThief {

    public static int stoi(String str) {
        return Integer.parseInt(str);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = stoi(st.nextToken()); // 보석 개수
        int K = stoi(st.nextToken()); // 가방 개수
        
        // 보석 정보 초기화
        int[][] jrs = new int[N][2];
        for (int i=0; i<N; i++) {
          StringTokenizer tempst = new StringTokenizer(br.readLine());
          jrs[i][0] = stoi(tempst.nextToken());
          jrs[i][1] = stoi(tempst.nextToken());
        }
        // 무게 기준으로 오름차순 정리
        Arrays.sort(jrs, (o1, o2) -> { return o1[0]-o2[0]; });
        
        // 가방 정보 초기화
        Integer[] bags = new Integer[K];
        for (int i=0; i<K; i++) {
          bags[i] = stoi(br.readLine());
        }
        // 수용량 기준으로 오름차순 정리
        Arrays.sort(bags);
        
        long sum = 0;
        int now = 0;
        PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
        for (int i=0; i<bags.length; i++) {
          long capacity = bags[i];
          
          while (now < jrs.length && jrs[now][0]<=capacity) {
            pQ.offer(jrs[now][1]);
            now++;
          }
          if (pQ.size() > 0) {
            long s = pQ.poll();
            sum += s;
          }
        }
        
        System.out.println(sum);

        br.close();
    }
}