[백준] 1202, 보석도둑 Java

1202, 보석 도둑

전형적인 그리디 문제라고 생각했다.

N,K <=300,000 이므로 nlog n 이하의 시간 복잡도로 해결해야한다.

또한, 보석의 최대 가치가 1,000,000 이며 30만개의 가방에 들어갈 수 있으므로 Long 자료형을 사용해야한다.

전략

이 문제에서 내가 선택한 그리디 전략은

1. 가방 무게를 오름차순으로 정렬한다.
2. 보석을 무게 순으로 정렬한다.
3. 가방무게를 초과하지않도록 보석을 넣어주되, 가방안에 들어가는 보석의 가치를 최대로 해준다.

위 전략을 구현하기 위해선 정렬이 필요하다.

그래서 nlog n 의 우선순위큐를 사용해 가방과 보석을 정렬해 준다.

그 다음, 가방을 순회하며 가방의 무게를 넘지 않으면서 최대 가치의 보석을 넣어 줘야한다.

그러기 위해선 하나의 전략이 더 필요하다.
왜냐하면 50,100,20 가치의 보석이 있을 때 가방에 100 보석이 들어가게 된다.
하지만 다음 가방에서 50 보석이 들어갈 수 있기 때문에 고려한 보석중 최대 가치를 가진 보석이 어떤 것인지 알아야한다.

그래서 나의 우선순위큐를 하나 더 사용하여 고려한 보석들을 넣어주고, 고려한 보석들 중 가장 가치가 큰 보석을 꺼내주었다.

전체 코드

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

public class Main {
    // 1202, 보석도둑
    // 그리디 전략 : 가방 무게가 w1이라고 하고 w1>w2이면 , 보석 무게가 wt라고 하면 wt<=w2가 될 떄 까지 w1에 들어갈 수 있는
    // 보석의 가치를 최대로 함.
    // 예를 들면 1. 무게 10인 가방을 먼저 채워넣음 2.무게 2인 가방에 들어 갈 수 있는 보석이 나올 떄 까지 보석 무게를 줄여가며 무게
    // 10가방의 가치를 최대로 만듬 3. 무한반복

    // 1.무게 순으로 가방 ,보석을 정렬함
    // 300,000 이므로 nlogn 정렬 필요 => 우선 순위 큐
    // 2. 보석 큐만큼 loop을 돌며 넣을 수 있는 가방에 최대의 보석가치가 되도록 함.
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken());
        long k = Long.parseLong(st.nextToken());
        long answer = 0;

        PriorityQueue<Tiffany> tiffanies = new PriorityQueue<Tiffany>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            long weight = Long.parseLong(st.nextToken());
            long value = Long.parseLong(st.nextToken());
            tiffanies.add(new Tiffany(weight, value));
        }
        PriorityQueue<Long> bags = new PriorityQueue<Long>();
        PriorityQueue<Tiffany_temp> tiffanies_temp = new PriorityQueue<Tiffany_temp>();

        for (int i = 0; i < k; i++) {
            bags.add(Long.parseLong(br.readLine()));
        }

        while (!bags.isEmpty()) {
            long bag = bags.poll();// 가장 작은 가방
            long max = 0;
            while (!tiffanies.isEmpty()) {
                Tiffany tiffany = tiffanies.peek();
                if (tiffany.weight > bag)
                    break; // 안 들어갈 경우
                tiffanies_temp.add(new Tiffany_temp(tiffany));
                tiffanies.poll();
            }

            if (!tiffanies_temp.isEmpty())
                answer += tiffanies_temp.poll().tiffany.value;
        }
        System.out.println(answer);
    }
}

class Tiffany implements Comparable<Tiffany> {
    long weight;
    long value;

    public Tiffany(long weight, long value) {
        this.weight = weight;
        this.value = value;
    }

    @Override
    public int compareTo(Tiffany o) {
        return Long.compare(this.weight, o.weight);
    }
}

class Tiffany_temp implements Comparable<Tiffany_temp> {
    Tiffany tiffany;

    public Tiffany_temp(Tiffany tiffany) {
        this.tiffany = tiffany;
    }

    @Override
    public int compareTo(Tiffany_temp o) {
        return -Long.compare(this.tiffany.value, o.tiffany.value);
    }
}