[백준]Greedy: 보석도둑

문제

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

상덕이가 털 보석점에는 보석이 총 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)

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

출력

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

 

문제 접근.

일단 하소연 부터..보석도둑이 아니라 내 시간 도둑이다.

로직 흐름은 간단하다.

 

각각 다른 무게&가치를 가진 보석과, 무게가 다른 가방이 주어졌을 때, 가방에 담는 보석의 가치가 최대일 때의 가치의 합을 찾으면 된다.

간단히 생각하면 한 가방에 최대로 담길 수 있는 최대의 가치를 찾아서 더해주면 된다.

 

• 어쨌든 가방의 무게와 , 보석의 무게를 비교해야 한다.
• 따라서 가방을 오름차순 정렬, 보석을 무게 기준으로 오름차순 정렬한다.
• 이제 가방에 대하여 반복문을 돌면서 해당 가방에 들어갈 수 있는 보석의 가치를 PriorityQueue에 넣어준다.
• 이 때, queue 가장 앞 쪽 보석은 현재 가방에 들어갈 수 있는 보석 중 가장 큰 가치를 나타낸다.

로직 흐름은 빨리 캐치했다. 하지만 시간초과가 나면서 이를 해결하는데 애를 먹었따.

 

• array를 쓸 수 있는데 ArrayList를 씀으로 인해서 속도가 저하되었다.
• 또한 queue에 값을 넣는 과정에서 이 전에 루프와 겹치지 않도록 하는 방법을 몰랐음.

 

풀이 코드

package baekjun;

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

public class _1202_v2 {

    public static class Jewel{
        long weight;
        long value;

        public Jewel(long weight, long value) {
            this.weight = weight;
            this.value = value;
        }
    }
    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());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        //ArrayList, array 속도차이?
        Jewel[] jewels = new Jewel[N];
        for (int i=0; i< N; i++){
            st = new StringTokenizer(br.readLine());
            jewels[i] = new Jewel(Integer.parseInt(st.nextToken()),  Integer.parseInt(st.nextToken()));
        }


        long[] bags = new long[K];
        for (int i=0; i< K; i++){
            bags[i] = Long.parseLong(br.readLine());
        }


        Arrays.sort(bags);

        Arrays.sort(jewels, new Comparator<Jewel>() {
            @Override
            public int compare(Jewel o1, Jewel o2) {
                if (o1.weight == o2.weight){
                    return (int) (o1.value - o2.value);
                }else{
                    return (int) (o1.weight - o2.weight);
                }
            }
        });

        PriorityQueue<Long> jewelsQueue = new PriorityQueue<>(Collections.reverseOrder());

        long answer = 0;
        int i=0; //i를 여기서 정의하면 while문 끝났을 때의 i부터 다시 시작됨. 먼저 탐색한 이후부터 이어서 탐색함.
        for (long bag : bags) { //무게 오름차순 가벼운거 -> 큰거
            while (i < N && jewels[i].weight <= bag){
                jewelsQueue.add(jewels[i++].value);
            }
          //Queue의 맨 앞은 현재 가방에 넣을 수 있는 보석 중,  가장 가치가 큰 보석
            if (!jewelsQueue.isEmpty()){
                answer+= jewelsQueue.poll();
            }

          //다음은 현재 가방보다 무거운 가방임.\
          //따라서 다음 가방 기준으로 보석을 넣을 때 무게가 더 무거운 보석이 추가 가능.
          //현재 추가된 보석 과, 다음에 추가될 보석 중 가장 가치가 큰 보석을 찾으면 됨.

        }

        bw.write(answer+"\n");
        bw.flush();
        bw.close();
        br.close();
    }

}