[백준] 1202 보석 도둑 - 우선순위큐 + 그리디 JAVA

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

1202번: 보석 도둑

코드설명

그리디와 우선순위큐 문제입니다.

 

보석에 가장 높은 가치의 보석을 담을 수 있는 방법은, 낮은 무게의 보석을 낮은 무게 순으로 되어있는 가방에 넣으면서 최대한 많은 보석을 넣는 것입니다. ( 큰 가방 먼저 낮은 무게를 넣기시작하면, 작은 가방에 넣을 수 있는 값이 큰 가방에 들어가면서 최대의 보석을 못담습니다. )

1. 주어진 보석을 무게는 오름차순 정렬, 무게가 같을시에는 가격은 내림차순으로 정렬합니다. (가벼운보석먼저 검사) 
2.  가방은 오름차순으로 정렬합니다. ( 작은 가방 먼저 보석을 넣기 위하여 )
3. 가방을 모두 순회하면서 해당 가방에 보석을 넣을 수 있는지 확인합니다. ( 이떄 이미 가방은 작은 무게에서 큰 무게로, 보석도 작은 무게에서 큰 무게로 정렬되어 있습니다. )
   1. 가방이 해당 보석의 무게보다 크거나 같다면, pq(가방) 에 해당 Value값을 넣습니다. ( pq는 최대힙인 상태입니다. 높은 가격이 먼저 우선순위가 있습니다.) 보석을 넣은뒤에는 해당 보석의 nodeIdx++ 작업을 통하여 다음 보석으로 이동합니다. 보석을 모두 순회할때까지 계속해서 진행합니다. 
   2. 만약 더이상 가방에 보석을 넣지 못한다면, 반복문을 종료하고, 현재 가방에 담아있는 무게 중 가장 높은 Value의 값을 answer에 더해줍니다. ( 이렇게 할경우 더 큰 가방에 만약 작은 무게의 보석이 들어온다고하더라도 이미 PQ에 최대힙 상태로 값이 남아있기에 각 가방에는 최대 무게의 보석을 넣을 수 있습니다. )

 

코드

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
	public static int N, K;
	public static int[] arr;
	public static int answer = 0;
	public static Node[] node;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	node = new Node[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		int weight = Integer.parseInt(st.nextToken());
    		int price = Integer.parseInt(st.nextToken());
    		
    		node[i] = new Node(weight, price);
    	}
    	
    	//무게에 대해서 오름차순 정렬, 무게가 같을시에는 가격을 내림차순으로 정렬
    	//이 작업을 통해서 보석의 무게가 가장 적은순으로 하고, 가격은 그에 맞추어 가장 큰 순으로 정렬됩니다.
    	Arrays.sort(node, new Comparator<Node>() {
    		@Override
    		public int compare(Node o1, Node o2) {
    			if(o1.weight > o2.weight) { //무게에 대해서 오름차순 정렬 (무게가 작은것부터 처리하기 위해)
    				return 1; 
    			}else if(o1.weight == o2.weight) { //무게가 같을시에는 가격을 가장 큰거 먼저 가져와야하므로 내림차순
    				if(o1.price < o2.price) { //가격은 내림차순 정렬
    					return 1; 
    				}else if(o1.price == o2.price){
    					return 0;
    				}else {
    					return -1;
    				}
    			}else {
    				return -1;
    			}
    		}
    	});
    	
    	int[] bags = new int[K];
    	for(int i=0;i<K;i++) {
    		st = new StringTokenizer(br.readLine());
    		bags[i] = Integer.parseInt(st.nextToken());
    	}
    	//큰 가방에 먼저 무거운 것을 담는다면, 작은 가방에는 아무것도 못담을 경우가 있습니다.
    	//가방의 무게를 오름차순으로 정렬합니다. (적은 가방 먼저 채우기 위해, 보석도 적은 무게 순으로 정렬)
    	Arrays.sort(bags);
    	
    	PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
    	long answer = 0;
    	int nodeIdx = 0;
    	for(int i=0; i<K;i++) {
    		int nowBagWeight = bags[i];
    		
    		while(nodeIdx < N) {
    			if(node[nodeIdx].weight <= nowBagWeight) { //현재 가방의 무게보다 정렬된 보석의 무게가 작다면, 해당 Value를 pq에 넣습니다.
    				pq.add(node[nodeIdx].price);
    				nodeIdx++;
    			}else {
    				break;
    			}
    		}
    		
    		if(!pq.isEmpty()) { //우선순위큐에는 value가 내림차순으로 되어있으므로 가장 큰 가격순으로 나옵니다. 그러므로 해당 가격을 해당 가방에 넣었다고 생각하고 넘어갑니다.
    			//가방은 무게가 커지는 순서이므로 이전에 넣었던 pq의 무게는 무조건 다음 bagWeight보다 작거나 큽니다. 
    			answer += pq.poll();
    		}
    		
    	}
    	
    	System.out.println(answer);
    }
    
}

class Node{
	int weight;
	int price;
	public Node(int weight, int price) {
		this.weight = weight;
		this.price = price;
	}
}