[Algorithm] 백준 B1202 보석도둑 JAVA

📌 문제

---

📌풀이

처음 봤을 때 N과 K의 범위가 300,000 이기 때문에 보석을 전부 가방에 넣어보는 식으로 구현하면 시간초과가 발생한다. 따라서 O(NlogN)의 시간복잡도로 접근해야한다.

 

생각해보면 풀이는 간단하다. 그리디적으로 생각해봤을때 각 가방에 들어갈 수 있는 보석들 중에서 가장 가치가 높은 보석을 가방에 넣으면 된다. 하지만 모든 보석을 각 가방마다 탐색하게 된다면 O(N^2)의 시간복잡도가 발생하게 된다. 따라서 가방을 정렬하고 보석들도 정렬한 후에 한 번 살펴본 보석들은 다시 안 보는 방식으로 구현하도록 해야한다.

 

1. 보석들 무게 순으로 정렬하기(오름차순, 같으면 비싼순으로)

2. 가방들 무게 순으로 정렬하기(오름차순)

3. 가장 가벼운 가방부터 보석의 무게와 비교하며 넣을 수 있는 보석은 우선순위 큐에 담기

4. 우선순위 큐에서 가장 가치가 높은 순으로 정렬된 첫번째값을 뽑아서 결과에 더해주기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str[] = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int K = Integer.parseInt(str[1]);
        ArrayList<Gold> golds = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            String str2[] = br.readLine().split(" ");
            golds.add(new Gold(Integer.parseInt(str2[0]), Integer.parseInt(str2[1])));
        }
        Collections.sort(golds, new Comparator<Gold>() {
            @Override
            public int compare(Gold o1, Gold o2) {
                if (o1.weight == o2.weight) {
                    return o2.value - o1.value;
                }
                return o1.weight - o2.weight;
            }
        });
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i=0;i<K;i++){
            queue.add(Integer.parseInt(br.readLine()));
        }
        PriorityQueue<Gold> getGolds = new PriorityQueue<>(new Comparator<Gold>() {
            @Override
            public int compare(Gold o1, Gold o2) {
                return o2.value-o1.value;
            }
        });
        long count =0;
        int i =0;
        while(!queue.isEmpty()){
            int bag = queue.poll();
            while(i<N && bag >= golds.get(i).weight){
                getGolds.add(golds.get(i));
                i++;
            }
            if(!getGolds.isEmpty()){
                count+=getGolds.poll().value;
            }
        }
        System.out.println(count);
    }

    public static class Gold {
        int weight;
        int value;

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

    }
}