[JAVA] 백준 1202 보석도둑

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

문제분석

자료구조가 2개 나온다. 가방 배열, 무게-보석 배열 2개다. 이 2개를 원시적으로 2번 순회(아래 왼쪽 그림)하게끔 작동했더니 왠걸 바로 시간초과가 발생했다. 시간 복잡도를 신경써야하는 문제였다. 따라서, 무게 기준으로 정렬하고, 무게를 기준으로 한번 순회를 진행하며, 가방 크기에 맞지 않는 보석으로 가면, pq에서 가격이 가장 비싼 보석하나를 가방에 넣고 다음가방으로 이동해서 진행한다.

 

코드

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

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());
        int[][] gems = new int[N][2];
        int[] bags = new int[K];

        for(int i = 0; i < N; i++){ // 보석
            String temp = br.readLine();
            String[] temps = temp.split(" ");
            int mi = Integer.parseInt(temps[0]);
            int vi = Integer.parseInt(temps[1]);
            gems[i][0] = mi; // 무게
            gems[i][1] = vi; // 가격
        }
        for(int i = 0; i < K; i++){ // 가방
            bags[i]=Integer.parseInt(br.readLine());
        }

        Arrays.sort(gems,(a,b)->{
            if(a[0]==b[0]){
                return a[1]-b[1];
            }return a[0]-b[0];
        }); // 1. 무게, 2. 가격 ASC 정렬
        Arrays.sort(bags);

        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a,b)->b[1]-a[1]); // pq는 가격 기준으로 DESC 정렬
        long result = 0;
        int i = 0;
        for (int cap : bags) {
            while (i < N && gems[i][0] <= cap) { // 가방에 들어갈 수 있는 보석들 추가
                pq.offer(gems[i]);
                i++;
            }
            if (!pq.isEmpty()) {
                result += pq.poll()[1];
            }
        }
        System.out.println(result);
    }
}