백준 1202번 - 보석 도둑 / Java

문제

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

1202번: 보석 도둑

처음에 정렬을 통해 보석을 가격이 높은순대로 내림차순 정렬하고, 가방은 오름차순으로 정렬해서

가방에 넣을수있는 보석을 모두 검사하는 방법을 가장 먼저 생각해냈다.

근데 보석과 가방의 제한이 300,000 인지라 이 방법대로하면 O(N^2)이 90,000,000,000 이라는 무지막지한 시간이 걸려서 시간초과가 뜬다.

그래서 탐색시간을 줄이기위해 TreeMap을 사용해 풀었다. TreeMap은 무게에 맞는 가방을 찾아내는데 O(logn)의 시간이 걸리므로 시간안에 문제를 해결할 수 있다.

 

알고리즘

1. 먼저 보석을 가격이높은순, 가격이같다면 무게가 낮은순으로 정렬한다

2. 가방의 무게를 TreeMap에 저장한다. 가방의 무게가 같은것이 여러개일 수 있으므로 Set이 아니라 Map을 사용한다

3. 보석을 넣을 가방의 최소무게를 찾고, answer에 보석의 가격을 추가한다. 보석을 넣은 가방의 개수를 1개빼준다.

소스코드

/*
 * BOJ1202
 * 2020.02.01
 * Hyeonseong
 */
import java.util.*;    
public class BOJ1202 {
    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
class Solution{
    int n,k;
    int gold[][];
    TreeMap<Integer,Integer> bag;
    long answer = 0;
    public Solution() {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        k = scan.nextInt();
        gold = new int[n][2];
        bag = new TreeMap<Integer, Integer>();
        for(int i=0;i<n;i++) {
            gold[i][0] = scan.nextInt();
            gold[i][1] = scan.nextInt();
        }
        for(int i=0;i<k;i++) {
            int a = scan.nextInt();
            if(bag.containsKey(a)) {
                bag.put(a,bag.get(a)+1);
            } else {
                bag.put(a,1);
            }
        }        
        Arrays.sort(gold, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) { // 가격내림차순, 가격이 같다면 무게 오름차순
                if(o1[1]==o2[1]) {
                    return o1[0]-o2[0];
                } else {
                    return o2[1]-o1[1];
                }
            }    
        });
        for(int i=0;i<n;i++) {
            SortedMap<Integer,Integer> temp = bag.tailMap(gold[i][0]); // 담을수 있는 가방의 리스트를 가져온다
            if(!temp.isEmpty()) { // 리스트가 비었다면 보석을 넣을 수 있는 가방이 없는 것
                answer += gold[i][1];
                int key = temp.firstKey(); // 가방의 리스트중 가장 용량이 작은 가방을 선택
                int value = temp.get(key);
                if(value==1) { // 가방이 1개라면 map에서 지워버린다
                    bag.remove(key);
                } else { // 가방이 여러개면 1개만빼서 다시 map에 넣는다
                    bag.put(key, value-1);
                }
            }
        }
        System.out.println(answer);
    }
}