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

백준알고리즘 1202번 : 보석 도둑

 

 

 

시간 초과와 RunTime Error를 반복한 끝에 성공했다.

우선순위큐(Priority Queue)의 중요성을 배운 문제이다.

이중for문(혹은 for문과 while문)을 사용하게 된다면 최대 30만*30만의 시간복잡도가 발생하게된다.

따라서 가방의 최대 무게외 보석의 정보 배열을 정렬했다고 하더라도

시간 제한이 걸리는 testCase가 발생하기 때문에.. 이 방식은 한 번 해보고 빠르게 접었다.

우선순위큐의 장점은, 내가 add한 Queue 중 최대값(혹은 최소값)을 poll할 수 있다는 점이다.

이는 인자들을 꾸준히 더하거나 빼야하는 상황이나
(특정 가방이 들수 있는 보석들을 모두 담고, 하나의 보석만 빼고 남겨둬야한다.)

인자들의 최대, 최소값을 구해야하는 상황에서
(담긴 보석들 중 가장 비싼 보석만 pick한다.)

ArrayList나 Stack, Queue, 배열 등을 사용하는 것보다 낮은 시간복잡도를 기대할 수 있다.

 

 

풀이 과정

---

1. 보석을 2차원 배열에 담고, 무게의 오름차순으로 정렬한다.
2. 가방의 최대 무게 배열도 오름차순으로 정렬한다.
3. 우선순위큐를 내림차순으로 정의한다.
4. 가방 배열만큼 for문을 돌려, 가방이 담을수 있는 최대 무게보다 덜 나가는 보석들은 모두
   우선순위큐에 담은 뒤, 우선순위큐의 최상위 값을 poll하고 다음 가방 배열로 넘어간다.
4-1. 가방이 담을 수 있는 보석이 없을 수도있으니, 적절한 예외처리를 해준다.
5. poll된 값들을 더하여 출력한다.

 

 

 

소스 ▽

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

public class Main {// No1202 보석 도둑
	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());// 가방의 갯수
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		Integer[] bags = new Integer[K];
		Integer[][] jewelry = new Integer[N][2];

		for (int i = 0; i < N; i++) {
			StringTokenizer st1 = new StringTokenizer(br.readLine());
			jewelry[i][0] = Integer.parseInt(st1.nextToken());
			jewelry[i][1] = Integer.parseInt(st1.nextToken());
		}

		for (int i = 0; i < K; i++) {
			bags[i] = Integer.parseInt(br.readLine());
		}

		Arrays.sort(jewelry, new Comparator<Integer[]>() {

			@Override
			public int compare(Integer[] o1, Integer[] o2) {
				return o1[0] - o2[0];
			}
		});

		Arrays.sort(bags);
		long ans = 0;

		int cnt = 0;
		for (int i = 0; i < bags.length; i++) {
			while (cnt < N && bags[i] >= jewelry[cnt][0]) {
				pq.add(jewelry[cnt][1]);
				cnt++;
			}

			if (!pq.isEmpty()) {
				ans += pq.poll();
			}
		}

		System.out.println(ans);

	}

}