백준 1202 보석 도둑(JAVA)

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

1202번: 보석 도둑

문제 분류: 그리디 알고리즘, 자료구조, 우선순위 큐, 정렬

 

 

문제 설명

첫번째 방법(틀린 방법)

보석의 우선순위 큐와 가방의 우선순위 큐를 만들고, 보석의 우선순위 큐의 경우는 가격이 높은 순으로, 가격이 같다면 무게가 가벼운 순으로 정렬을 하고, 가방의 경우는 내림차순으로 정렬.

그리고 두개의 큐 중 하나라도 빌때까지 while 문을 돌리면 된다 생각했다.

하지만, 다른 무게에서 충분히 넣을 수 있는데, 가장 많이 넣을 수 있는 가방에 넣어버리는 반례가 존재했다.

 

두번째 방법

일단 큐로는 절대 안된다 생각하여 리스트나 배열을 써야겠다 생각했다.

그리고 O(n*k)의 방법으로는 시간초과가 나기에 O(nlogn) 방법을 생각했어야 했다.

 

그렇게 생각했던게, 먼저 두개의 리스트를 정렬한다. 보석의 경우는 위에서 정렬했던 것과 같이하고,

가방의 경우는 오름차순으로 정렬을 한다.

그리고 각 가방의 무게에 넣을 수 있는 물건을 우선순위 큐에 넣고,

큐에 가장 앞에 있는 것이 가장 비싼 물건이니 그것을 더하는 식으로 하는 방법을 생각하여 맞았다.

 

전체 코드

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


public class Main {

    static class Item implements Comparable<Item>{
        int m;
        int v;

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

        @Override
        public int compareTo(Item o){
            if(this.m == o.m) return o.v - this.v;
            else return this.m - o.m;
        }
    }
    public static void main(String[] args) throws NumberFormatException, 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());

        List<Item> itemList = new ArrayList<>();
        List<Integer> bagList = new ArrayList<>();

        for(int i = 0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            itemList.add(new Item(m,v));
        }

        for(int i = 0;i<k;i++) bagList.add(Integer.parseInt(br.readLine()));

        Collections.sort(itemList);
        Collections.sort(bagList);
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        int index = 0;
        long cnt = 0;
        for(int i = 0;i<k;i++){
            while (index<n && itemList.get(index).m <= bagList.get(i)){
                queue.add(itemList.get(index).v);
                index++;
            }

            if(!queue.isEmpty()) cnt+=queue.poll();
        }
        System.out.println(cnt);
    }
}