BOJ1202 보석도둑

<문제 요약>

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

1202번: 보석 도둑

(1) 총 N 개의 보석 각 보석에는 무게 M, 가격 V를 가지고 있다.

(2) 가방은 K개 가방에 담을 수 있는 최대 무게는 C, 가방에는 한 개의 보석만 넣을 수 있다(가방 무게랑 같거나 작은 보석)

(3) 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하시오

 

<풀이흐름, Source Code>

보석의 가격이 큰 순서로 정렬, 가방의 무게가 가벼운 순서로 정렬

보석을 한개 씩 빼서 가방에 넣을 수 있는지 검사 → 둘다 정렬된 상태이기 때문에 보석을 다 넣으면 가장 최선으로 넣은거임

(1) 보석의 가격이 큰 순서로 정렬을 한다. 처음에는 구조체(weight, price)를 갖는 단순 배열을 생각했지만, 보석과 가방의 개수가 30만개이고 단순 배열의 Arrays.sort는 QuickSort로 최악의 경우 n^2의 시간복잡도이다.

그래서 다음에 생각한건 list를 사용해서 Collections.sort하는 방법, 이건 MergeSort를 사용해서 nLog(n)의 시간 복잡도를 갖는다.

list를 사용해서 해도 되지만 Pro시간에서는 가능하면 HeapSort를 사용하기 위해 HeapSort를 사용하는 우선순위큐를 사용. 우선순위큐에 add할 때 가격순으로 정렬하기 위해 compareTo()를 사용한다.

(2) 가방무게는 무게가 작은 순서로 정렬을 한다. 처음에는 역시 단순 배열을 생각했지만, 보석한개를 꺼내서 30만개의 가방을 다 탐색한다면 n^2의 시간복잡도가 나오기 때문에 이분탐색을 해야된다. 이분탐색을 위해서 TreeMap사용

(3) 이제 보석큐에서 한 개 꺼내서 가방트리 중 같거나 큰 값중 가장 작은 무게를 갖는 가방에 넣는다. ceillingKey()

넣을 수 있는 가방이 있으면 result에 누적합 해주고 bagCount를 갱신

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class BOJ1202_보석도둑 {
	
	private static class Node implements Comparable<Node>{
		int weight;
		int price;
		Node(int weight, int price){
			this.weight = weight;
			this.price = price;
		}
		@Override
		public int compareTo(Node o) {
			return this.price <= o.price ? 1 : -1;
		}
	}
	static int N, K, M, V, C;
	static PriorityQueue<Node> pq = new PriorityQueue<>();
	static TreeMap<Integer, Integer> tm = new TreeMap<Integer, Integer>();
	
	public static void main(String[] args) throws IOException{
		input();
		System.out.print(cal());
	}

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		for(int in = 0; in < N; in++) {
			st = new StringTokenizer(br.readLine(), " ");
			M = Integer.parseInt(st.nextToken());
			V = Integer.parseInt(st.nextToken());
			pq.add(new Node(M, V));
		}
		for(int ik = 0; ik < K; ik++) {
			st = new StringTokenizer(br.readLine(), "");
			C = Integer.parseInt(st.nextToken());
			if(tm.containsKey(C)) {
				tm.put(C, tm.get(C) + 1);
			}
			else {
				tm.put(C, 1);
			}
		}
	}

	private static long cal() {
		long result = 0;
		while(!pq.isEmpty()) {
			Node n = pq.poll();
			int weight = n.weight;
			int price = n.price;
			if(tm.ceilingKey(weight) == null) {
				continue;
			}
			else {
				int bagWeight = tm.ceilingKey(weight);
				int bagCount = tm.get(bagWeight);
				if(bagCount > 0) {
					result += price;
					bagCount--;
					if(bagCount <= 0) {
						tm.remove(bagWeight);
					}
					else {
						tm.put(bagWeight, bagCount);
					}
				}
			}
		}
		return result;
	}
}

 

<문제 Issue>

(1) int는 -21억~21억이다. 처음에 result를 int로 설정 했는데 보석은 최대 30만개이고 가격은 최대 100만

그럼 result에 들어갈 수 있는 최대는 30만 * 100만이여서 21억을 훌쩍 넘는다. 그래서 result는 long으로 선언

 

<중요 정리>

(1) sort 들

Arrays.sort → Quick Sort 사용 최악의 경우(반대로 정렬) n^2의 시간 복잡도

Collections.sort → Merge Sort 사용 항상 nLog(n)의 시간 복잡도를 유지

우선순위 큐 → Heap sort 사용 nLog(n) 시간 복잡도

프로시험에서는 최대한 Heap sort를 사용하도록 하자

(2) implements Comparable

compareTo{

return this.price <= o.price

}

는 this.price가 현재 add하는 놈이고 o.price가 이미 자료구조 안에 있는 놈

o.price가 크면 return 1, this.price가 크면 return -1