[백준] 보석 도둑 /자바

문제         

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

레벨: G2
알고리즘: 그리드 
풀이시간: 40분
힌트 참조 유무: 무

1 번째 시도   

• 보석의 가격으로 정렬해야 하나? 
• 보석의 무게로 정렬해야 하나?
• 가격으로 정렬 후 가방 순회하며 담을 수 있는 지 판단
• 자료구조 고민
  •  현재 가방에서 선택할 수 있는 보석을 우선순위큐에 넣기 
  • 우선순위 큐를 보석의 값으로 내림차순 정렬
  • 가장 보석의 값이 큰 거 하나 선택
  • 이 과정을 가방의 개수 만큼 반복

import java.util.*;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        int n = scan.nextInt();
        int k = scan.nextInt();
        
        ArrayList<Gem> list = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            int m = scan.nextInt();
            int v = scan.nextInt();
            list.add(new Gem(m, v));
        }
        Collections.sort(list, (o1, o2) -> o1.m - o2.m); //무게순 정렬
        
        int[] weight = new int[k];
        for(int i = 0; i < k; i++) {
            weight[i] = scan.nextInt();
        }
        Arrays.sort(weight);
        
        long total = 0;
        int listIdx = 0;
        PriorityQueue<Gem> pq = new PriorityQueue<>((o1, o2) -> o2.v - o1.v); //가격순 정렬
        for(int i = 0; i < k; i++) {
            while(listIdx < n && list.get(listIdx).m <= weight[i]) {
                Gem current = list.get(listIdx++);
                pq.add(new Gem(current.m, current.v));
            }
            if(!pq.isEmpty()) total += pq.poll().v;
        }
        System.out.println(total);
    }
    
    public static class Gem {
        int m;
        int v;
        
        public Gem(int m, int v) {
            this.m = m;
            this.v = v;
        }
    }
}