백준 1202 [보석 도둑] - JAVA

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

1202번: 보석 도둑

 

풀이

1. 보석 무게를 기준으로 오름차순 정렬하고 무게가 같을경우 가격기준 내림차순으로 정렬한다.

2. 가방 무게를 기준으로 오름차순 정렬한다.

  => 보석 가격의 합이 최대가 되려면 가방보다 무게가 작으면서 가격은 제일 비싼 보석을 담아야한다.

3. PriorityQueue를 사용하여 무게가 작으면서 가장 비싼 보석을 찾아낸다.

 

※ 주의사항

- 범위를 확인하고 type를 지정하자.

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)
다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

최댓값이 들어왔다고 생각했을때 K = 300000, 보석의 가치가 모두 Vi = 1000000 일경우

보석 가치의 합은 300,000,000,000이 되게된다.

int 범위 : -2147483648 ~ 2147483647
long 범위 : -9223372036854775808 ~ 9223372036854775807

 

 

소스코드

package algorithm.greedy;

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

/**
 * 보석 도둑
 */
public class Q1202 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input[] = br.readLine().split(" ");
		int N = Integer.parseInt(input[0]);
		int K = Integer.parseInt(input[1]);
		//int 범위 -2147483648 ~ 2147483647
		//long 범위 -9223372036854775808 ~ 9223372036854775807
		long nAnswer = 0;
		
		//보석 무게 오름차순으로 정렬
		Jewel jewelArr[] = new Jewel[N];
		for(int nIdx = 0 ; nIdx < N ; nIdx++) {
			input = br.readLine().split(" ");
			jewelArr[nIdx] = new Jewel(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
		}
		Arrays.sort(jewelArr, new Comparator<Jewel>(){
			@Override
			public int compare(Jewel o1, Jewel o2) {
				if (o1.weight > o2.weight) { 
					return 1; 
				}else if (o1.weight < o2.weight) { 
					return -1; 
				}else if (o1.weight == o2.weight) {
					if(o1.value > o2.value) {
						return -1;
					}else if(o1.value < o2.value) {
						return 1;
					}else 
						return 0;
				}
				return 0;
			}
		});
		
		//가방 무게 오름차순으로 정렬
		PriorityQueue<Integer> bagQu = new PriorityQueue<Integer>();
		for(int nIdx = 0 ; nIdx < K ; nIdx++) {
			bagQu.add(Integer.parseInt(br.readLine()));
		}
		
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Comparator.reverseOrder());
		int nArrIdx = 0;
		while(!bagQu.isEmpty()) {
			//1.선택
			//2.적절성 검사
			int nBagWeight = bagQu.poll();
			
			//보석 무게 오름차순으로 정렬 / 가방 무게 오름차순 정렬
			//하였기에 우선순위큐안에 들어있는 보석들은 다음 가방에 담길 수 있다.
			while(nArrIdx < jewelArr.length && nBagWeight >= jewelArr[nArrIdx].weight) {
				pq.add(jewelArr[nArrIdx].value);
				nArrIdx++;
			}
			
			if(pq.size() > 0) {
				nAnswer += pq.poll();
			}
			
		}
		
		System.out.println(nAnswer);

	}

}

class Jewel {
	int weight;
	int value;
	
	public Jewel (int weight, int value) {
		this.weight = weight;
		this.value = value;
	}
	
}