백준 1202 보석 도둑 Java

정답률 23퍼센트의 그리디 문제인 보석 도둑 문제이다.

보석의 개수 N개와 가방의 개수 M개가 주어지고 보석의 무게와 가격이 주어지며 가방에 담을 수 있는 무게의 양도 주어진다.

단 가방에는 하나의 보석밖에 넣을 수 없다.

N과 M의 최댓값은 300,000으로 O(NM)의 시간복잡도로는 문제를 풀 수 없다. 다시 말해서 보석을 가격이 비싼 순으로 정렬하고 가방을 무게가 가벼운 순으로 정렬해서 이중 for문으로 가벼운 가방에 비싼 보석의 무게를 비교해보며 푸는 방식은 시간 초과가 나온단 말이다.

물론 나는 시간 초과가 나올 줄 알면서도 한 번 해봤다 ㅎ

이 문제를 시간초과 없이 해결하려면 PriorityQueue를 사용해야 한다.

PriorityQueue는 우선순위 큐로 들어간 값에 우선순위를 매겨서 정렬이 된다. PriorityQueue에 여러 개의 값을 넣을 경우엔 오름차순으로 자동 정렬된다고 생각하면 된다.

쉽게 말해서 감옥에 죄수들을 넣었다고 하면 형량이 작은 사람부터 감옥을 나오므로 형량이 작은사람 부터해서 오름차순으로 큐에 정렬된다.

결론적으로 이 문제를 푸는 방법은

1. 보석을 무게순으로무게 순으로 오름차순 정렬, 가방을 무게 순으로 오름차순 정렬

2. 가방을 기준으로 for문을 돌려서 그 가방에 넣을 수 있는 모든 보석의 가격을 우선순위 큐에 넣는다.

3. for문 한번당 우선순위 큐의 가장 위에 있는 가장 비싼 보석의 가격을 더한다.

위에서 말했던 PriorityQueue는 우선순위가 오름차순으로 정렬된다.

하지만 우리는 가격이 비싼 보석부터 정답에 더해야 하므로 우선순위를 내림차순으로 정렬해야 한다.

PriorityQueue를 내림차순으로 하는 법은 간단하다. 가격을 넣을 때 -1을 곱해주고 넣으면 된다.

그리고 우선순위에서 빼서 더할때 Math.abs()로 절댓값을 더해주면 된다.

가방도 보석도 무게순으로 오름차순 정렬되어있기 때문에 가방에 담을 수 있는 보석을 큐에 모두 넣고 가장 비싼 것만 더하고 다음 가방에도 앞에서 담은것을 제외하고 담을 수 있는 모든 보석을 큐에 넣고 가장 비싼 것만 더하고 이런식으로 문제를 해결해 나갈 수 있다.

큐에서 삽입과 삭제는 O(1)이기 때문에 비슷하게 자동 정렬을 구현해주는 TreeSet을 이용하는 것보다 효율적이다.

따라서 이과정의 시간 복잡도는 O(M+N)으로 시간 안에 통과할 수 있다.

주의해야 할점은 보석의 최대 가격이 1억이기 때문에 가격을 더할 변수를 long으로 선언해야 한다.

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

public class Q1202 {

    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Jewelry [] a = new Jewelry[n];
        int [] bag = new int[m];

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(reader.readLine());
            a[i] = new Jewelry(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        for(int i=0; i<m; i++) {
            bag[i] = Integer.parseInt(reader.readLine());
        }

        Arrays.sort(a);
        Arrays.sort(bag);

        Queue<Integer> q = new PriorityQueue<>();
        long ans = 0;
        int j = 0;
        for(int i=0; i<m; i++) {
            while(j < n && a[j].c <= bag[i]) { //앞에서 담은것은 제외해야 하므로 while문과 j를 사용
                q.add(-a[j].v);
                j++;
            }
            if(!q.isEmpty()) { //for문 한번에 한번만 더한다.
                ans+=Math.abs(q.poll());
            }
        }
        System.out.println(ans);
    }
}

class Jewelry implements Comparable<Jewelry> {
    int c;
    int v;

    public Jewelry(int c, int v) {
        this.c = c;
        this.v = v;
    }

    @Override
    public int compareTo(Jewelry o) {
        return  this.c - o.c;
    }
}