[백준] 1202 보석 도둑 #JAVA #우선순위 큐

[백준] 1202 보석 도둑 #JAVA #우선순위 큐

 

---

코드

---

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

public class Main {

	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); //보석 정보 개수
		int K = Integer.parseInt(st.nextToken());
		
		//1. 보석의 무게, 가치를 담는 우선순위 큐 정의
		PriorityQueue<int[]> pQ = new PriorityQueue<int[]>((a,b)->{
			if(a[0]-b[0] == 0) {
				return b[1]-a[1]; //가치 내림차순 정렬
			}
			return a[0]-b[0];//무게 오름 차순 정렬
		});
		
		//1-1. 우선순위 큐에 보석 정보 저장	
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			int M = Integer.parseInt(st.nextToken()); //보석 무게
			int V = Integer.parseInt(st.nextToken()); //보석 가격
			
			pQ.add(new int[] {M,V});
			
		}
		
		//2. 가방 정보 저장하는 List
		List<Integer> bag = new ArrayList<Integer>();
		for (int i = 0; i < K; i++) {
			int C = Integer.parseInt(br.readLine()); //가방 최대 무게 
			bag.add(C);
		}
		//2-1. 가방 오름차순 정렬
		Collections.sort(bag);
		
		
		//3. 가방에 들어갈 수 있는 무게를 valueQ로 옮긴후 가장 가치가 큰 값을 total에 더한다.
		PriorityQueue<Integer> valueQ = new PriorityQueue<Integer>(Collections.reverseOrder());
		long total = 0;
		for (int i = 0; i < bag.size(); i++) {
			int weight = bag.get(i);
			
			while (!pQ.isEmpty()) {
				 
				if(pQ.peek()[0] <= weight) {
					valueQ.add(pQ.poll()[1]); //가치만 넣는다.
				}else {
					break;
				}
			}
			
			if(valueQ.isEmpty()) continue;
			total += valueQ.poll();
			
			
		}

		
		System.out.println(total);
		
		
	}

}

 

 

풀이

---

그리디 알고리즘기반으로 무게와 가치를 고려해야 하다보니 꽤 복잡하여 고생한 고전한 문제입니다. 

제한 시간이 1초로 시간초과와의 싸움이였습니다.(넘나 싫은 것,,)

 

실패한 방법은,

1. TreeMap을 사용하여 <Integer(가치), 우선 순위 큐> 를 사용하여 보석의 정보를 저장합니다. 

2. 가장 가치가 큰 값을 담을 가장 작은 가방 탐색을 실시합니다.

    2-1. 가방을 정렬 후 이분탐색을 실시하여 under bound 값을 찾기

결과는 시간 초과 였습니다.(logN x logN + logN 맞나?)

 

다른 방법을 찾아 시도 하여 성공하였습니다.

 

1. 우선순위 큐에 보석 정보를 담습니다. <int[]>

    1-1. [0]번 인덱스는 M(무게) [1]번 인덱스는 V(가치)가 담기도록 합니다.

    1-2. 무게는 오름 차순으로 정렬되고, 가치는 내림차순으로 정렬되게 합니다. (가볍고, 비싼거 먼저!)

2. 가방 정보를 List에 담습니다. (정리하며 생각해보니 배열도 됩니다 헤헤)

    2-1. 가방을 오름차순으로 정렬합니다. (2, 5, 10, ··· )

3. 가장 작은 가방부터 순회하며 가장 높은 가치의 물건을 담도록 합니다.

    3-1. 새로운 우선순위 큐 <Integer>를 생성한다. 

    3-2. 인자는 V(가치)가 내림차순으로 정렬되게 한다.

    3-3. 가장 작은 가방에 들어갈 수 있는 가장 큰 가치의 보석을 하나씩 담는다.

 

 

 

---

※참고: 우선순위 큐의 시간복잡도 IN 자바

시간 복잡도	메서드
O(log(n))	offer, poll, remove, add
O(n)	remove
O(1)	peek, element, size

 

 

주의 사항

---

• total 변수는 long이여야 합니다. 가방 300,000개가 보석 가치 1,000,000을 담게 되면 int의 범위를 초과하게 됩니다.

 

반례

---

INPUT 1

3 2 5 20 7 25 8 50 5 5

OUTPUT 1

20

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)