[JAVA] 백준 1202번- 보석 도둑

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

1202번: 보석 도둑

 

package DAY03.P1202;

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

public class Main {
    public static class Jewel implements Comparable<Jewel>{
        int weight, price;
        public Jewel(int weight, int price){
            this.weight = weight;
            this.price = price;
        }
        @Override
        public int compareTo(Jewel o){ // 무게 오름차순
            return this.weight - o.weight;
        }
    }
    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> jewels = new ArrayList<>();
        List<Integer> bagWeights = new ArrayList<>();

        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); // 보석 가격 내림차순

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            jewels.add(new Jewel(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        for(int i=0; i<k; i++){
            bagWeights.add(Integer.parseInt(br.readLine()));
        }
        // 가방 무게 오름차순, 보석 무게 오름차순
        Collections.sort(bagWeights);
        Collections.sort(jewels);

        int idx = 0;
        long answer =0;
        for(int bagWeight : bagWeights){
              while(idx<n && jewels.get(idx).weight <= bagWeight){ // 보석 무게가 가방 무게보다 작거나 같으면
                  pq.offer(jewels.get(idx++).price); // 큐에 보석 가격을 넣는다. 
              }
              if(!pq.isEmpty()) answer+=pq.poll();
        }
        System.out.println(answer);
    }
}

 

가방과 보석(무게 기준)을 오름차순 정렬한다.

그리고 가방과 보석을 처음부터 비교하면서 보석 무게가 가방무게보다 작거나 같으면 큐에 넣는다.

우선순위큐는 보석 가격 내림차순으로 정의해 가격이 높은것부터 빠져나오게 된다.

 

 

시간복잡도

 

가방 무게 정렬시 O(nlogn), 보석 정렬시 O(nlogn)이다. 

 

n개의 보석을 큐에 넣는것은 O(nlogn)이다.

(힙 삽입시 한번 넣는 연산이 O(logn)이고 n개의 보석을 넣으므로)

 

그리고 가장 비싼 보석을 빼는 것은 O(nlogn)이다.

(가방 개수를 n개라고 했을 때, n번 삭제하기 때문이다.)

 

다 더하면 총 4nlogn -> nlogn의 시간복잡도를 가진다.