메리

처음 시도 

1. 보석의 무게와 가격을 이중배열에 담는다.
2. 보석 2중배열을 가격을 기준으로 내림차순 정렬
3. 가방 무게 배열을 오름차순 정렬
4. 가방 배열과 보석 배열 이중 for문, 조건 : 보석무게 <= 가방무게인 경우 가격을 +, 값은 -1 세팅
=> 이중 for문으로 모든 가방마다 보석배열을 쭉 돌게 됨

결과 : 시간초과

2차 시도

1. 보석의 무게와 가격을 이중배열에 담는다.
2. 보석 2중배열을 가격을 기준으로 내림차순 정렬 무게 기준 오름차순 정렬
3. 가방 무게 배열을 오름차순 정렬
4. 가방 배열 순회 for, 보석 배열 순회 while, 조건 : 보석무게 <= 가방무게인 경우 
가격을 우선수위 큐에 담고 보석배열 인덱스 증가시킴. 보석 배열은 한 번만 순회함.
가방에 담을 수 있는 보석 중 가장 비싼 가격을 뽑아서 +.

결과 : 시간초과

3차 시도

1. 보석의 무게와 가격을 담는 이중배열에 담는다.  객체를 만든다.
2. 보석 객체 배열 무게 기준 오름차순 정렬
3. 가방 무게 배열을 오름차순 정렬
4. 가방 배열 순회 for, 보석 배열 순회 while, 조건 : 보석무게 <= 가방무게인 경우 
가격을 우선수위 큐에 담고 보석배열 인덱스 증가시킴. 보석 배열은 한 번만 순회함.

가방에 담을 수 있는 보석 중 가장 비싼 가격을 뽑아서 +.

결과 : 통과

* 이중배열과 객체배열을 사용하는 것의 시간 차이가 있는 것으로 보임

* 우선순위 큐 최대 힙

PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

* 배열 정렬에 Comparator 사용

Arrays.sort(jewels,Comparator.comparingInt((int[] a)->a[0]));

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        //목적 최대한 비싼 보석 넣기
        Scanner sc = new Scanner(System.in);
        int jewelCnt = sc.nextInt();
        int bagCnt = sc.nextInt();

        //보석 무게와 가격 정보
        Jewelry[] jewels = new Jewelry[jewelCnt];
        for(int i=0; i<jewelCnt; i++){
            Jewelry temp = new Jewelry(sc.nextInt(), sc.nextInt());
            jewels[i] = temp;
        }

        //보석 무게 오름차순
        Arrays.sort(jewels, Comparator.comparingInt(j -> j.mass));

        //가방 정보
        int[] bagInfo = new int[bagCnt];
        for(int i=0; i<bagCnt; i++){
            bagInfo[i] = sc.nextInt();
        }
        //가방 무게 적은 순 정렬
        Arrays.sort(bagInfo);        
        
        long sum = 0;
        int jewelIndex = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        for (int bag : bagInfo) {
            // 현재 가방 무게에 맞는 모든 보석을 추가
            while (jewelIndex < jewels.length && jewels[jewelIndex].mass <= bag) {
                pq.offer(jewels[jewelIndex].price);
                jewelIndex++;
            }
            // 가장 비싼 보석 선택
            if (!pq.isEmpty()) {
                sum += pq.poll(); // 선택된 보석은 다른 가방에서 사용되지 않음
            }
        }
        
        System.out.println(sum);
    } 
}

class Jewelry {
    int mass; // 무게
    int price; // 가격
 
    Jewelry(int mass, int price) {
        this.mass = mass;
        this.price = price;
    }
}