백준 1202 보석 도둑 JAVA + TreeMap이용.

문제 : 보석 도둑 

난이도 : 골드 2 / 1초/ 256MB

문제 :

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

 

입력 -

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

 

 

 

해결 

 

그리디로 해결하였다. 

가격이 높은 순대로 가방 무게가 있는지 확인하였고, 

맞는 가방 무게가 있을시, 가장 가벼운 가방부터 없앴다. 

 

1) 보석 객체를 선언하여 가격 기준 내림차순 정렬, 가격이 같다면 무게를 오름차순 정렬하였다. 

(사실, 가격이 같을 때에는 무게 어떤 기준으로 정렬하여도 둘다 맞다고 뜬다. )

 

2) 가방 정렬은 TreeMap<int, int>로 구현하여 자동으로 정렬하도록 했다. 

Key : 가방 무게 value : 갯수 (무게가 같은 가방이 있을 수 있으므로)

 

3) treeMap.higerKey(key) -> key값의 높은 가격들 중 가장 가까운 key들의 key 반환. 

 

import java.io.*;
import java.util.*;
import java.util.Map.Entry;

class Jew {
	int m, v;
	Jew(int m, int v) {
		this.m = m;
		this.v = v;
	}
	
}
public class Main {

	public static void main(String[] args) throws Exception {		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		Jew[] jew = new Jew[n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int m = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			jew[i] = new Jew(m, v);
		}
		
		/* 가격 정렬 ~~ */
		Arrays.sort(jew, new Comparator<Jew>() {
			@Override
			public int compare(Jew j1, Jew j2) {
				if (j1.v == j2.v) {
					return j1.m-j2.m;
				} else {
					return j2.v-j1.v;
				}
			}
		});
		
		TreeMap<Integer, Integer> bag = new TreeMap<>();
		for (int i = 0; i < k; i++) {
			int c = Integer.parseInt(br.readLine());
			if (bag.containsKey(c)) {
				bag.put(c, bag.get(c)+1);
			} else bag.put(c, 1);
		}
		
		long price = 0; //가격 long타입으로 해줘야 전부 TC통과.
		for (int i = 0; i < n; i++) {
			Jew j = jew[i];
			int m = j.m;
			int c = -1;
            
			if (bag.containsKey(m)) {
				c = m;
				int next = bag.get(c);
				if (next > 1) bag.put(c, next-1);
				else bag.remove(c);
				price+=j.v;
			} else {				
				if (bag.higherKey(m) == null) continue;
				c = bag.higherKey(m);
				int next = bag.get(c);
				if (next > 1) bag.put(c, next-1);
				else bag.remove(c);
				price += j.v;
			}
			
		}
		System.out.println(price);
	}
	
}