[백준 #3067] 보석 도둑 - JAVA(자바)

문제

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

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

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

해설

그리디 문제이다.

 

보석의 최대 가격을 훔쳐야 하니 보석의 가격을 기준으로 내림차순으로 정렬해서 가장 비싼 보석을 가방에 넣을 수 있는지 확인한다.

이때 가방은 그 보석이 들어갈 수 있는 가장 작은 가방을 선택하면 된다. 따라서 코드에서는 TreeMap 자료구조를 이용해서 celilngKey() 함수를 사용했다. 이 함수는 key 값보다 큰 값 중 가장 작은 값을 반환한다. 시간은 O(nlogn) 이다. 그럼 보석의 무게가 들어갈 수 있는 가장 작은 무게의 가방을 사용할 수 있고 코드는 그대로 구현하면 된다.

 

그리고 TreeSet 이 아닌 TreeMap 을 사용하는 이유는 중복 key 값 때문이다. 그래서 TreeMap 의 <key,value> 는 <가방 무게, 중복 개수> 이다. 그래서 코드를 보면 가방을 사용할 때 개수가 1개 보다 많으면 replace() 함수로 중복 개수 - 1 을 하고 가방 개수가 1이면 remove() 함수를 쓴다. 

 

시간은 전체 O(nlogn) 이 소요된다. 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] jewels = new int[n][2];

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 2; j++){
                jewels[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        TreeMap<Integer, Integer> tMap = new TreeMap<>(); // <가방 최대 무게, 중복 개수>
        for(int i = 0; i < k; i++){ // O(KlogK)
            int weight = Integer.parseInt(br.readLine());
            tMap.put(weight, tMap.getOrDefault(weight, 0) + 1);
        }

        Arrays.sort(jewels, (o1,o2) -> o2[1] - o1[1]); // 비싼게 앞으로(내림차순 정렬) O(NlogN)

        long answer = 0;
        for(int i = 0; i < n; i++){ // O(NlogK)
            int[] jewel = jewels[i];
            Integer bag = tMap.ceilingKey(jewel[0]); // jewel의 무게보다 큰 것 중 가장 작은 무게, 또는 같은 무게
            if(bag != null){
                answer += jewel[1];
                int cnt = tMap.get(bag); // 중복 개수
                if(cnt > 1){
                    tMap.replace(bag, cnt - 1);
                }else{
                    tMap.remove(bag);
                }
            }
        }
        System.out.print(answer);
    }
}