백준 1202번 - 보석 도둑

문제

백준 1202번 - 보석 도둑

아이디어

• 매순간, 현재 가방에 넣을 수 있는 보석 중 가장 가치가 높은 보석을 더하는 그리디 알고리즘을 적용하여 해결한다.
• 가방을 오름차순, 보석을 무게 기준으로 오름차순 정렬한다.
• 각 가방에 대해 넣을 수 있는 보석의 가치를 우선순위 큐에 넣는다. 이때, 우선순위 큐는 내림차순 정렬이다.
• 그리고 우선순위 큐에서 값을 하나 빼서 누적합에 더해준다.

예상 시간 복잡도

• 가방 정렬 : O(NlogN)
• 보석 정렬 : O(KlogK)
• 보석의 가치 우선순위 큐 관리 : O(KlogK)
• 예상 시간 복잡도 : O(NlogN + KlogK)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ_1202 {
    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[] bags = new int[k];
        Jewel[] jewels = new Jewel[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            int m = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            jewels[i] = new Jewel(m, v);
        }

        for (int i = 0; i < k; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(bags);   //가방 정렬
        Arrays.sort(jewels); //보석 무게기준 정렬

        //내림차순 정렬 우선순위 큐
        PriorityQueue<Integer> qu = new PriorityQueue<>(Collections.reverseOrder());

        long sum = 0;
        int index = 0;

        for (int i = 0; i < k; i++) {
            while (index < n && bags[i] >= jewels[index].m) { //현재 가방에 넣을 수 있는 보석의 가치 저장
                qu.offer(jewels[index].v);
                index++;
            }
            if (!qu.isEmpty()) { //우선순위 큐로 가장 큰 값 빼냄
                sum += qu.poll();
            }
        }

        System.out.println(sum);

    }

    static class Jewel implements Comparable<Jewel> {

        int m, v;

        public Jewel(int m, int v) {
            this.m = m;
            this.v = v;
        }

        @Override
        public int compareTo(Jewel o) {
            if (this.m == o.m) {
                return o.v - this.v;
            }
            return this.m - o.m;
        }
    }
}

• 가격의 합의 최댓값은 300,000 x 1,000,000이 될 수 있으므로 long을 사용한다.