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

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

1202번: 보석 도둑

풀이

이번 문제는 간단한 수학으로 풀 수 있는 문제라고 생각할 수 있지만 보석의 개수와 가방의 무게의 범위가 커서 시간 초과가 발생할 것이다.

 

시간 초과 에러를 발생시키지 않으려면 우선순위 큐를 이용해야 한다.

우선순위 큐는 여러 개의 값이 들어있을 경우 오름차순으로 자동 정렬된다고 생각하면 된다.

 

문제 해결 과정은 아래와 같다.

1. 보석을 무게 순으로 오름차순, 가방을 무게 순으로 오름차순 정렬한다.

2. 가방에 들어갈 수 있는 보석을 추출해서 우선순위 큐에 넣는다.

3. 한 가방에 하나의 보석만 넣을 수 있으므로 for문을 돌리면서 우선순위 큐에서 하나만 뽑아낸다.

 

우선순위 큐는 기본적으로 오름차순 정렬로 뽑아낸다. 하지만 이 문제에선 내림차순 정렬로 뽑아내야한다.

필자는 보석을 추출해서 우선순위 큐에 넣을 때 음수로 입력해줬다.

음수로 입력하게 되면 내림차순으로 쉽게 정렬할 수 있다.

 

이후에 우선순위 큐에서 뽑아낼 때 Math.abs()를 이용해서 절대값으로 뽑아내면 된다.

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

public class Main {
    public static class Jewelry implements Comparable<Jewelry>{
        int w;
        int v;
		
        public Jewelry(int w, int v) {
            this.w = w;
            this.v = v;
        }
		
        public int compareTo(Jewelry o) {
            return this.w - o.w;
        }
    }
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int jewelryCnt = Integer.parseInt(st.nextToken()); // 보석 개수
        int bagCnt = Integer.parseInt(st.nextToken());     // 가방 개수
		
        Jewelry[] jewelry = new Jewelry[jewelryCnt]; // 보석
		
        for (int i=0; i<jewelryCnt; i++) {
            st = new StringTokenizer(br.readLine());
			
            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            jewelry[i] = new Jewelry(w, v);
        }
		
        int[] bags = new int[bagCnt];
        for (int i=0; i<bagCnt; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }
		
        Arrays.sort(jewelry); // 보석 무게 오름차순으로 정렬
        Arrays.sort(bags);    // 가방에 담을 수 있는 무게 오름차순으로 정렬
		
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        long ans = 0; // 가격이 1억이 넘기 때문에 long 타입으로 선언
        int j = 0;
        for (int i=0; i<bagCnt; i++) {
			
            // 현재 가방에 들어갈 수 있는 무게의 보석을 우선순위 큐에 입력
            while (j < jewelryCnt && jewelry[j].w <= bags[i]) {
                pq.add(-jewelry[j].v);
                j++;
            }
			
            // 가방 하나에 보석 하나만 넣을 수 있음
            if (!pq.isEmpty()) {
                ans += Math.abs(pq.poll());
            }
        }
		
        System.out.println(ans);
    }
}