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

 

---

 

• 생각

1. 가방에 넣을 수 있는 보석을 차례대로 dfs로 넣는다? => 모든 경우의 수를 다 탐색한다. 정확하지만 시간초과의 가능성 존재

 

2. 가방의 무게가 수용할 수 있는 최소 무게 가방부터 넣을 수 있는 보석을 확인 후 넣을 수 있는 최대의 가격 보석을 넣는다. 

tip) 2차원 배열 정렬

 

• 코드

정답 코드 : 1번 방법은 시간초과가 나올 것 같아서 2번 방법을 시행했다. 2번 방법을 쉽게 푸는 팁이 있다면 array.sort로 배열을 오름차순으로 정렬 후 pritorityqueue 우선순위 큐(큐에 있는 값들이 2개 이상이면 오름차순으로 큐에 들어감)를 사용하여 쉽게 해결할 수 있었다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, K;
	static int[][] jewelry;
	static int[] bag;
	static long maxValue;

	public static void main(String[] args) throws Exception {
		SetData();
		FindMaxValue();
		System.out.println(maxValue);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		maxValue = 0;
		jewelry = new int[N][2];
		bag = new int[K];

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

		for (int i = 0; i < K; i++)
			bag[i] = Integer.parseInt(br.readLine());

		// 2차원 배열 sort
		Arrays.sort(jewelry, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[0] - o2[0];
			};

		});
		Arrays.sort(bag);
	}

	private static void FindMaxValue() {
		// 우선 순위 큐로 해야지 오름차순 정렬이 되서 작은 값이 맨 먼저 나오게됌
		Queue<Integer> queue = new PriorityQueue<>();
		int j = 0;
		for (int i = 0; i < K; i++) {
			while (j < N && jewelry[j][0] <= bag[i]) { // 앞에서 담은것은 제외해야 하므로 while문과 j를 사용
				queue.add(-jewelry[j][1]);	// -를 해주는 이유는 -를 해야지 양수 최대값이 음수로 넣었을 때 오름차순에서 맨 앞으로 가져올 수 있게한다. 
				j++;
			}
			if (!queue.isEmpty()) { // for문 한번에 한번만 더한다.
				maxValue += Math.abs(queue.poll());	// 음수로 바꿔줬던 수에 절대값을 씌워서 양수로 다시 나오게함
			}
		}

	}
}