[코테] 백준 1202번 : 보석 도둑 (java)

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

알고리즘 분류 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐

 

❓문제

---

🔅해석

조건이 2개 이상이므로 우선순위 큐(PQ)를 사용하여 문제를 풀이한다.

 

보석의 속성이 2가지 있으므로 객체로 생성하여 짝을 이룰 수 있게한다.

 

가방에 넣을 수 있는 보석을 PQ에 담기 위해 가방과 보석의 무게를 오름차순 정렬한다.

 

이후 반복문을 돌면서 정답을 계산한다.

1. 가방을 하나 고른다.

2. 무게순으로 정렬한 보석을 해당 가방에 들어갈 수 있는지 비교하고 들어갈 수 있다면 해당 보석을 PQ에 넣는다.

3. 한 가방에 다 넣었으면 PQ에서 보석을 꺼내어 해당 보석의 가격을 정답에 더한다.

 

---

⭕정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static int N, K;

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

		// 가격 최대 힙
		PriorityQueue<Jewel2> pq = new PriorityQueue<>(Comparator.comparing(Jewel2::getValue).reversed());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		List<Jewel2> juwerl = new ArrayList<>();
		int[] bag = new int[K];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int w = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			juwerl.add(new Jewel2(w, v));
		}

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

		// 가방 오름차순 정렬
		Arrays.sort(bag);

		// 보석 무게 오름차순 정렬
		Collections.sort(juwerl, (o1, o2) -> o1.weight - o2.weight);

		// 가방에 넣을 수 있는 보석을 pq에 넣음
		int idx = 0;
		long result = 0;
		for (int i = 0; i < K; i++) {
			while (true) {
				if (idx < N && bag[i] >= juwerl.get(idx).weight) {
					pq.add(juwerl.get(idx++));
				} else {
					break;
				}
			}

			if (!pq.isEmpty()) {
				// 이 때의 pq의 top의 의미는 가방에 넣을 수 있는 가장 비싼 보석.
				result += pq.poll().value;
			}
		}

		System.out.println(result);

		br.close();
	}

}

class Jewel2 {
	int weight;
	int value;

	public Jewel2(int weight, int value) {
		super();
		this.weight = weight;
		this.value = value;
	}

	@Override
	public String toString() {
		return "[weight=" + weight + ", value=" + value + "]";
	}

	public int getWeight() {
		return weight;
	}

	public int getValue() {
		return value;
	}
}

 

---

❗결과