[JAVA] BOJ 백준 1202 보석도둑

풀이

1. 처음 보석을 입력 받고 compareTo 함수를 이용하여 보석을 가벼운 순으로 정렬한다.
2. 이때 무게가 같다면 더 가치있는 것을 앞에 오게 한다.
3. 가방을 priorityQueue에 저장하여 가벼운 순으로 정렬되게 한다.
4. 가방을 pq에서 뽑은 다음 findJewel에 해당 가방보다 작은 보석만 넣어주도록 for문을 통해 갱신해준다.
5. findJewel은 가치가 높은 순으로 정렬된다.
6. 해당 가방에 넣을 후보 보석이 아예 없을 수 있으므로 findJewel이 empty인 경우 continue 처리를 한다.
7. pq를 통해 뽑은 보석은 그 중 가장 가치있는 보석이므로 바로 result에 더해준다.

전체 코드

import java.io.*;
import java.util.*;

public class Main {
	static class jewel implements Comparable<jewel>{
		int weight;
		int value;

		public jewel(int weight, int value){
			this.weight = weight;
			this.value = value;
		}

		@Override
		public int compareTo(jewel jewel) {
			int r = Integer.compare(this.weight, jewel.weight);
			if(r == 0)
				r = -Integer.compare(this.value, jewel.value);
			return r;
			// 가벼운 거 >> 더 가치있는 거
		}
	}
	static PriorityQueue<Long> bags;
	static PriorityQueue<jewel> findJewels;
	static int K;
	public static void main(String[] args) throws Exception{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		jewel[] jewels = new jewel[N];
		findJewels = new PriorityQueue<>((o1, o2) -> -Integer.compare(o1.value, o2.value));
		bags = new PriorityQueue<>();
		for(int i=0; i<N; i++){
			st = new StringTokenizer(bf.readLine(), " ");
			jewels[i] = new jewel(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}

		Arrays.sort(jewels);

		for(int i=0; i<K; i++)
			bags.offer(Long.parseLong(bf.readLine()));

		int i = 0; long result = 0;

		while(!bags.isEmpty()){
			long b = bags.poll();
			for(; i<N; i++){
				if(b < jewels[i].weight) break;
				findJewels.offer(jewels[i]);
			}
			if(findJewels.isEmpty()) continue;

			jewel j = findJewels.poll();
			result += j.value;

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