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

#1202 보석 도둑

난이도 : 골드 2

유형 : 자료 구조 / 우선순위 큐 / 그리디

1202번: 보석 도둑

▸ 문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

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

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

▸ 출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

문제 풀이  

처음에는 그냥 배낭 문제로 배낭의 크기에 맞는 보석들을 넣어서 뽑아주면 될줄 알았지만 시간초과로 많이 고생했다. 결국 우선순위 큐와 정렬을 적절하게 사용하여 시간초과를 벗어났다. 한 번 과정을 살펴보자.

 

📚 조건

• 보석 N, 가방 K  ( 1 ≤ N, K ≤ 300,000 )
• 보석 정보 M, V ( 0 ≤ M, V ≤ 1,000,000 )
• 가방 최대 무게 C (1 ≤ C ≤ 100,000,000)

 

구상

그리디 문제로 최적해를 선정하는 방식을 구상해야 한다. 보석의 최대 가격을 훔치기위해서 도둑은 현재 가방에 넣을 수 있는 보석들 중에서 가장 큰 값을 가지는 보석을 넣어주면 된다. 예제 2번을 예로 들어보자. 용량이 2인 가방에 (무게, 가격)인 보석 (1,65) (2,99) 둘 중 하나를 넣어야 된다면 도둑은 무겁더라도 더 비싼 가격을 가진 (2,99)인 보석을 넣을 것이다. 그리고  두 번째 가방인 용량 10인 가방에 (1,65)와 (5,23)을 넣어도 용량이 남기 때문에 두 보석을 넣게 된다.

 

시간초과 코드

기본적으로 브루트포스로 돌리게 되면 O(NK)의 시간복잡도가 발생하여 시간초과가 발생한다. 

시간초과 발생 코드 O(NK)

long answer = 0;
int jIdx=0;
for(int i=0; i<k; i++) { // O(K)
	while(true) { // O(N)
		if(jIdx > jewInfo.size()-1) break;
		Jewel j = jewInfo.get(jIdx);
		if(bag[i]>= j.weight) {
			answer+= j.price;
			jIdx++;
			break;
		}
	}
}

 

O(K)는 모든 배낭을 무조건 한번씩은 조회하므로 줄일 수 없다. 그래서 여기서 줄일 수 있는 부분은 O(N)부분이다. 정렬과 우선순위 큐를 사용해서 줄여줄 것이다. 기준은 보석의 가격이 아닌 무게로 삼는다. 왜냐하면 보석 가격이 제일 비싸더라도 우선적으로 가방과 보석의 무게의 조건이 성립해야 보석을 담을 수 있기 때문이다.

 

조건을 보면 가방 최대 무게 C는 100,000,000이고, 보석의 최대 무게는 1,000,000으로 100배 정도의 크기가 차이나는 것을 볼 수 있다. 그렇다면 확률적으로 가방 하나 당 보석 한 개씩 탐색하게 되는 최악의 경우의 수가 나올 확률은 굉장히 낮아진다.

(뇌피셜이니 그냥 흘러넘겨도 된다.) 확률은 무작위이지만 각 발생확률을 1이라고 가정한다면 가방이 1의 무게를 가질 경우 1%, 또 그 1% 중에서 값을 비교했을 때 작은 값을 가질 경우는 선형확률보다 낮을 것이다. 

 

우선순위 큐와 정렬을 사용한 while문의 시간복잡도를 O(W)라 하자. O(W)는 선형탐색 K보다 작고 가방 1개가 보석 2개 이상을 비교할 확률이 높은 비선형적 탐색을 한다.

따라서,  W는 x축(k)가 커지면 함수 값도 커지지만 k의 최댓값이 되어도 커져도 선형함수(K)>=W 이므로, W'(dW/dk)는 x축(k)이 커질수록 함수 크기가 더 작아지는 비선형함수라고 추측 할 수 있다. 그렇다면  0<W<K 이므로, O(W) < O(K)로 로그 시간복잡도와 비슷한 높은 효율성을 기대할 수 있다. 

 

스케치

1. 가방, 보석 데이터를 무게를 기준으로 오름차순 정렬

예제 2번의 가방과 보석의 정보를 무게 기준으로 오름차순으로 정렬해보자.

• Arrays.sort(bag); // 가방 무게 오름차순 
• Collections.sort(jewInfo); // 보석 무게 기준 오름차순 

가방 i	1	2
무게	2	10

보석 j	1	2	3
무게	1	2	5

 

만약 가방 2에 보석이 1 2가 다 들어갈 수 있다는 뜻은 뒤에 10에도 들어갈 수 있음을 나타낸다. 그러면 탐색은 더이상 선형탐색이 아니게 된다.  

• i=1, 1번 가방 탐색(2) → 보석 1 2 탐색
• i=2, 2번 가방 탐색(10) → 보석 5 탐색

 

2. 최소 힙 (우선순위 큐) 사용하기

최소 힙을 사용하는 이유는 데이터를 넣을 때 마다 자동으로 정렬을 해주기 때문에 따로 또 데이터를 정제시킬 필요없이 가방 탐색이 끝날 때 마다 루트노드로 갈수록 값이 커지는 최소 힙(우선순위 큐)를 사용하여 큐의 맨 앞에 있는 보석의 정보를 꺼내주면 된다. 

• if(!pq.isEmpty()) answer += Math.abs(pq.poll());

 

풀이 코드 

시간복잡도에 대해 다시 한번 깊게 생각해볼 수 있는 문제였다.

• 시간복잡도 코드 설계 전략 보러가기

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		List<Jewel> jewInfo = new ArrayList<>();
		int[] bag = new int[k];
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int m = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			jewInfo.add(new Jewel(m,v));
		}
		
		for(int i=0; i<k; i++) {
			bag[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(bag); // 가방 무게 오름차순 
		Collections.sort(jewInfo); // 보석 무게 기준 오름차순 
		
		Queue<Integer> pq = new PriorityQueue<>((o1,o2) -> (o2-o1));
		long answer = 0;
		int j=0;
        
		// i : 가방 탐색 (0~k)
		for(int i=0; i<k; i++) {
	
			while(true) {
				if(j>=n) break;
				Jewel jew = jewInfo.get(j);
				
				if(bag[i] < jewInfo.get(j).weight) break;
				// 보석의 무게가 가방보다 작으면 최소 힙에 저장
				pq.add(jew.price);
				j++; // 보석 탐색 수count
			}
			// 최소 힙 맨 앞에 있는 숫자 꺼내줌 (가장 비싼 보석)
			if(!pq.isEmpty()) {
				answer += Math.abs(pq.poll());
			}
		}
		System.out.println(answer);
	}
}

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

	@Override
	public int compareTo(Jewel o) {
		return this.weight - o.weight;
	}
	
}