[백준] 1202. 보석 도둑 (Java)

 

문제

1202번: 보석 도둑

 

알고리즘

그리디 알고리즘, 정렬, 우선순위 큐

 

풀이

N과 K가 30만으로 굉장히 크기 때문에 O(n²) 의 미만의 시간 복잡도로 해결해야한다.

이를 위해서 정렬과 우선순위 큐를 사용한다.

 

준비물

1. 남아있는 보석을 저장할 우선순위 큐 remains (무게 기준 오름차순 정렬)

2. 담을 수 있는 보석을 저장할 우선순위 큐 avails (비용 기준 내림차순 정렬)

3. 가방을 저장할 리스트 bags (가방 용량 기준 오름차순)

 

알고리즘

1. 이제 모든 보석을 remains에 삽입하고, 모든 가방을 bags에 삽입한 후  용량의 오름차순으로 정렬한다.

2. 이제 용량이 낮은 가방부터 탐색하며 remains에서 해당 가방의 용량보다 무게가 작은 보석을 꺼내 avails 큐에 삽입한다.

이렇게 하면 avails에 있는 맨 앞의 원소는 해당 가방에 담을 수 있는 보석 중 가장 가격이 비싼 보석이 된다.

3. 따라서 맨 앞의 원소를 꺼내 값을 더한다.

 

이제 다음 가방을 탐색해도 해당 가방의 용량보다 가벼운 보석들이 이미 avails 큐에 담겨있기 때문에 보석을 처음부터 탐색하지 않아도 된다.

 

 

코드

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

public class Main {
	private static final String ArrayList = null;

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


		PriorityQueue<Jewel> remains = new PriorityQueue<>((j1, j2) -> j1.m - j2.m);
		PriorityQueue<Jewel> avails = new PriorityQueue<>((j1, j2) -> -(j1.v - j2.v));
		ArrayList<Integer> bags = new ArrayList<>();
		
		
		st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int M = Integer.parseInt(st.nextToken());
			int V = Integer.parseInt(st.nextToken());

			remains.add(new Jewel(M, V));
		}

		for (int i = 0; i < K; i++) {
			int C = Integer.parseInt(br.readLine());
			bags.add(C);
		}
		Collections.sort(bags);
		
		long sum = 0;
		for(int i=0; i<K; i++) {
			int cur = bags.get(i);
			while(!remains.isEmpty() && remains.peek().m <= cur) {
				avails.add(remains.poll());
			}
			
			if(!avails.isEmpty())
				sum += avails.poll().v;
		}
		
		System.out.println(sum);
	}

	static class Jewel {
		int m, v;

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