[백준] 골드 2 보석도둑

가방에 알맞는 보석을 찾는다..

브루트포스로 찾는 알고리즘을 구현했지만.. 시간초과가 발생했다.

 

정렬을 잘 이용해서

가방과 보석을 비교할때, 이미 비교한 보석은 다시 비교하지 않도록 로직을 구성해주었다.

 

가방은 무게를 기준으로 오름차순 정렬하고,

보석도 무게를 기준으로 오름차순을 정렬하되, 무게가 같은 경우에는 내림차순으로 정렬하도록 구현해주었다.

 

가방에 담을수 있는 보석들은 우선순위 큐를 사용해서

제일 가격이 비싼 보석을 찾는데 들어가는 비용을 줄이고자 우선순위 큐를 사용해서 구현해주었다.

 

package 큰돌의터전알고리즘강의.five주차.보석도둑;

import java.io.*;
import java.util.*;
 // 3프로 시간 초과
public class Main {

    public static class Jewelry{
        int weight;
        int price;

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

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

        Jewelry[] jewelries = new Jewelry[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());

            jewelries[i] = new Jewelry(weight,price);
        }

        Arrays.sort(jewelries, new Comparator<Jewelry>() {
            @Override
            public int compare(Jewelry o1, Jewelry o2) {

                if(o1.weight == o2.weight){
                    return o2.price - o1.price;
                }

                return o1.weight - o2.weight;
            }
        });

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

        Arrays.sort(bags); // 오름 차순 정렬

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        long ans = 0;
        for (int i = 0, j = 0; i < K; i++) { // 가방을 하나씩 확인하면서

            while(j < N && jewelries[j].weight <= bags[i]){ // j는 처음부터 x
                pq.offer(jewelries[j++].price);
            }

            if(!pq.isEmpty()){ // pq가 비어있지 않은 경우
                ans += pq.poll(); // 제일 무게가 무거운 친구
            }
        }

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

 

요부분에서 가방과 보석을 일일히 다 돌아주는 것이아니라

j라는 변수를 두어 이미 확인한 보석은 건너뛰는 형식으로 구현하느 것이 중요하다.!

for (int i = 0, j = 0; i < K; i++) { // 가방을 하나씩 확인하면서

            while(j < N && jewelries[j].weight <= bags[i]){ // j는 처음부터 x
                pq.offer(jewelries[j++].price);
            }

            if(!pq.isEmpty()){ // pq가 비어있지 않은 경우
                ans += pq.poll(); // 제일 무게가 무거운 친구
            }
        }