BOJ - 보석 도둑

1202 보석 도둑 : https://www.acmicpc.net/problem/1202

---

Problem

---

Solve

주어진 보석과 담을 수 있는 가방을 모두 비교하여 최대값을 구할 수 있지만, O(N^2)의 시간복잡도가 발생하기 때문에 시간초과가 발생하게됩니다.

가방이 담을 수 있는 무게가 작은 순으로 해당 가방에 담을 수 있는 보석의 정보를 넣어줍니다.
그 중 보석의 가격이 가장 큰 보석을 선택하여준다면, 각 가방에 넣을 수 있는 보석 중 최대 가격만 합쳐서 값을 구해낼 수 있게 됩니다.

그렇기 때문에 우선적으로 해야하는 것은, 가방이 담을 수 있는 보석의 무게를 기준으로 오름차순 정렬(bags), 보석의 무게를 기준으로 정렬(jewelries), 가방에 담을 수 있는 보석의 가격을 기준으로 내림차순 정렬(PQ)을 수행해주어야 합니다.

오름차순 정렬된 가방을 순차적으로 탐색하면서 보석 가격 기준 내림차순 정렬하는 PQ에 해당 가방이 담을 수 있는 보석을 보석 무게순으로 정렬되어있는 보석들을 이동하면서 넣어줍니다.
그리고 해당 가방에서 PQ에 보석이 들어있다면 보석 중 가격이 가장 높은 보석을 꺼내어 값에 적용시켜줍니다.

---

Code

import java.io.*;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Comparator;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		//주어진 보석
		Jewelry[] jewelries = new Jewelry[N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int M = Integer.parseInt(st.nextToken());
			int V = Integer.parseInt(st.nextToken());
			jewelries[i] = new Jewelry(M, V);
		}

		//보석 크기 기준 오름차순 정렬
		Arrays.sort(jewelries, new Comparator<Jewelry>() {
			@Override
			public int compare(Jewelry o1, Jewelry o2) {
				return o1.m-o2.m;
			}
		});

		//가방이 담을 수 있는 보석
		int[] bags = new int[K];

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

		//담을 수 있는 무게 기준 오름차순
		Arrays.sort(bags);

		//가방을 돌면서 각 가방에 담을 수 있는 보석들
        //보석의 가격 기준 내림차순
		PriorityQueue<Jewelry> pq = new PriorityQueue<>((o1, o2) -> {
			return o2.v - o1.v;
		});

		long answer = 0;
		int jIndex = 0;
		for (int i = 0; i < K; i++) {
        	//해당 가방이 담을 수 있는 보석들을 순차적으로 돌면서 보석을 저장
			while (jIndex < N && bags[i] >= jewelries[jIndex].m) {
				pq.offer(jewelries[jIndex++]);
			}

			//해당 가방에서 담을 수 있는 보석이 존재한다면 그 중 가장 가격이 높은 보석 가격 합산
			if (!pq.isEmpty())
				answer += pq.poll().v;
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static class Jewelry {
		int m;
		int v;

		public Jewelry(int m, int v) {
			this.m = m;
			this.v = v;
		}
	}
}

---

Result

---

Reference

https://steady-coding.tistory.com/56