[백준] 1202번 보석 도둑 자바

문제

 

1202번: 보석 도둑

 

 

문제 풀이

 

처음에는 보석을 기준으로 ArrayList와 PriorityQueue를 이용해서 가장 비싼 것부터 제거해나갔는데 시간초과였다.

구글링을 해보니 보석을 기준으로 하는게 아니라 가방을 기준으로 해야 했고, 또 우선순위큐 하나로 구현이 가능했다.

 

✔️알고리즘

1. 보석을 무게가 가벼운 순으로 정렬을 한다 (오름차순)

2. 가방을 가벼운 순으로 정렬을 한다 (오름차순)

3. 모든 가방에 대하여 반복문을 수행한다 -> 일단 가방에 보석이 들어갈 수 있으면 최대치로 다가갈 수 있기 때문에

3-1) 해당 가방 무게에 들어갈 수 있는 보석을 우선순위큐에 모두 넣는다

3-2) 이때, 우선순위큐는 보석 가격 내림차순으로 구현한다

3-3) 그러면 우선순위큐에는 해당 가방에 들어갈 수 있는 보석 중에 가장 비싼 것부터 나오게 된다

4. 다음 반복문에서도 해당 가방 무게에 들어갈 수 있는 모든 보석을 넣는다.

4-1) 이때 가방 무게가 오름차순이고, 큐는 우선순위가 구현되어 있으므로 보석을 누적해서 넣어줘도 된다

 

❗주의할 점은 보석의 무게가 1,000,000 이하이고, 가방 개수도 최대 300,000이므로 정답은 long타입으로 받아야 한다.

 

 

소스 코드

 

public class b_1202 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		
		long answer = 0;
		int N = Integer.parseInt(str[0]);	//보석 개수
		int K = Integer.parseInt(str[1]);	//가방 개수

		int[] C = new int[K];	//가방 수용 무게
		Jewelry[] jews = new Jewelry[N];
		PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());	//내림차순
		
		//보석 정보 입력
		for(int i = 0; i < N; i++) {
			str = br.readLine().split(" ");
			jews[i] = new Jewelry(Integer.parseInt(str[0]), Integer.parseInt(str[1]));
		}
		
		//가방 정보 입력
		for(int i = 0; i < K; i++)
			C[i] = Integer.parseInt(br.readLine());

		Arrays.sort(C);		//가방은 오름차순 (가벼운 것부터)
		Arrays.sort(jews);	//보석 무게 오름차순 (가벼운 것부터)
		
		for(int i = 0, j = 0; i < K; i++) {	
			while(j < N && jews[j].weight <= C[i])
				pq.offer(jews[j++].price);
			
			if(!pq.isEmpty())
				answer += pq.poll();
		}
		
		System.out.println(answer);
	}

}

class Jewelry implements Comparable<Jewelry>{
	int weight, price;
	
	public Jewelry(int weight, int price) {
		this.weight = weight;
		this.price = price;
	}

	@Override
	public int compareTo(Jewelry arg0) {
		if(this.weight > arg0.weight)
			return 1;
		else
			return -1;
	}

}