[백준] 1202 보석 도둑 (그리디) - Java

 

1202번: 보석 도둑

 

문제 설명

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

 

접근법

처음 접근 : 가장 비싼 보석을 가장 가벼운 가방에 넣는 방식

• 보석의 무게, 보석의 가격으로 이루어진 Jewel 클래스를 보석의 가격 내림차순으로 우선순위 큐에 넣음
• 가방의 무게를 오름차순으로 정렬
• 우선순위 큐에서 하나씩 꺼내 for문을 돌며 보석이 들어갈 수 있는 가장 가벼운 가방 찾음
• 시간복잡도 O(NM) → 시간초과

 

두번째 접근

• 보석의 정보와 가방의 무게를 각각 리스트에 저장
• 보석리스트 - 보석 무게를 기준으로 오름차순 정렬
• 가방리스트 - 오름차순 정렬
• 가방리스트 탐색(가방 무게가 작은것부터) : 해당 가방에 담을 수 있는 모든 보석의 가격을 우선순위 큐에 넣음
• 우선순위 큐(내림차순 기준)에서 값을 꺼내면 해당 가방에 넣을 수 있는 가장 비싼 보석
• 가방 1개당 우선순위 큐에서 값을 1개씩 꺼내서 가격 합에 더해줌

 

예제

 

우선순위 큐에 가격이 높은 순으로 저장

→ 가방 1개마다 우선순위 큐에서 값을 1개씩 꺼내서 sum에 더해줌

→ sum = 65

 

sum = 65+100 = 165

 

sum = 165 + 99 = 264

 

 

문제 풀이

시간초과 (가장 비싼 보석을 가장 가벼운 가방에 넣는 방식) - O(NM)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static PriorityQueue<Jewel> pq;

    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());

        pq = new PriorityQueue<>();
        List<Integer> maxWeightList = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.valueOf(st.nextToken());
            int price = Integer.valueOf(st.nextToken());
            pq.offer(new Jewel(weight, price));
        }

        for (int i = 0; i < K; i++) {
            maxWeightList.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(maxWeightList);

        int sum = 0;

        while (!pq.isEmpty()){
            Jewel jewel = pq.poll();
            int weight = jewel.weight;
            int price = jewel.price;

            for (int i = 0; i < maxWeightList.size(); i++) {
                int maxWeight = maxWeightList.get(i);
                if(maxWeight >= weight){
                    sum += price;
                    maxWeightList.remove(i);
                    break;
                }
            }
        }

        System.out.println(sum);

    }
    static class Jewel implements Comparable<Jewel> {
        private int weight;
        private int price;

        public Jewel(int weight, int price){
            this.weight = weight;
            this.price = price;
        }

        @Override
        public int compareTo(Jewel o) {
            return Integer.compare(o.price, this.price);
        }
    }
}

 

통과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    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());

        List<Jewel> jewelList = new ArrayList<>();
        List<Integer> bagWeight = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.valueOf(st.nextToken());
            int price = Integer.valueOf(st.nextToken());
            jewelList.add(new Jewel(weight, price));
        }

        for (int i = 0; i < K; i++) {
            bagWeight.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(jewelList);
        Collections.sort(bagWeight);

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        long sum = 0;
        int idx = 0;
        for (int i = 0; i < bagWeight.size(); i++) {
            while (idx < N && jewelList.get(idx).weight <= bagWeight.get(i)){
                pq.offer(jewelList.get(idx).price);
                idx++;
            }
            if(!pq.isEmpty()){
                sum += pq.poll();
            }
        }

        System.out.println(sum);

    }
    static class Jewel implements Comparable<Jewel> {
        private int weight;
        private int price;

        public Jewel(int weight, int price){
            this.weight = weight;
            this.price = price;
        }

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