[Java] 백준 1202번. 보석도둑 (골드2)

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

1202번: 보석 도둑

 

 

보석도둑 문제입니다.

핵심 아이디어는, 가방에 담을 수 있는 가장 비싼 보석을 담자! (Greedy)입니다.

다만 고려해야할 상황이 몇 개 있습니다.

 

우선 큰 가방에 비싼 보석을 담는다면 작은 가방에 아무것도 담지 못하는 비효율적인 상황이 생길 수 있습니다.

그러니 작은 가방을 먼저 채우는것이 좋습니다.

 

둘째, 가방의 갯수가 30만개, 보석의 가격이 100만까지 가능하므로 최대 3000억의 값이 정답으로 나올 수 있습니다.

정답을 long (C계열의 경우 longlong) 타입으로 선언해 주어야 오버플로우가 발생하지 않을 것 같습니다.

 

셋째, 보석과 가방의 갯수를 자세히 보시면... 둘 사이에는 부등호가 없습니다.

즉 가방이 보석보다 많을 수도 있다는 뜻입니다.

저는 이 부분을 놓쳐서 NullPoint Exception을 한 번 보았네요.

 

 

풀이로 들어가겠습니다.

작은 가방부터 넣을 수 있는 최대의 보석을 담습니다. 

저는 그래서 보석과 가방의 정보를 모두 받고, 둘을 모두 오름차순으로 정렬해 주었습니다.

 

그리고 정렬된 가장 가벼운 가방부터 담을 수 있는 가장 비싼 보석을 찾는데,

보석의 정보가 이미 정렬되어 있으므로 한 번 순회하며 자기가 담을 수 있는 보석까지만 PriorityQueue에 넣었습니다.

PriorityQueue의 Comparator를 람다식으로 설정해서 가치가 높은 보석이 위로 올라오게 했으므로 이 PriorityQueue안에는 내가 담을 수 있고 가장 비싼 보석이 위에 존재하게 됩니다.

PriorityQueue에서 보석 하나를 꺼내어 담는 처리를 하고 (정답에 누적합하고) 다음 크기의 가방에 대해 같은 작업을 반복하면 됩니다. 

 

좀 더 최적화된 방법이 있을것 같은데 나중에 생각나면 포스팅을 업데이트 하도록 하겠습니다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		PriorityQueue<int[]> pqueue = new PriorityQueue<int[]>((e1, e2) -> {
			return e2[1] - e1[1];
		});
		int[][] jewels = new int[N][2];
		int[] bags = new int[K];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			jewels[n][0] = Integer.parseInt(st.nextToken());
			jewels[n][1] = Integer.parseInt(st.nextToken());
		}

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

		Arrays.sort(jewels, (e1, e2) -> {
			return e1[0] - e2[0];
		});
		Arrays.sort(bags);

		int index = 0;
		long answer = 0;

		for (int k = 0; k < K; k++) {
			int nowBag = bags[k];

			while (index < N) {
				if (jewels[index][0] <= nowBag) {
					pqueue.add(jewels[index].clone());
					index++;
				} else {
					break;
				}
			}
			if(!pqueue.isEmpty()) {
				answer += pqueue.poll()[1];
			}
		}

		System.out.println(answer);
	}
}