[백준] 1202번 보석 도둑

문제 설명

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

문제 풀이

• 첫번째 생각한 방식은 다음과 같다.

  1. 가방을 용량 순으로 정렬한다.
  2. 보석을 가치의 역순으로 정렬한다.
  3. 보석을 하나씩 꺼내고 이분탐색(lower bound)로 용량에 맞는 가방을 찾으면 결과에 더해준다.

• 이러한 방식은 보기에는 O(NlogN)의 풀이 같지만 3번 과정에서 가방을 리스트에서 제거해주는 과정이 필요하여 결국 O(N^2) 방식이 되어 시간초과가 났다.
• 통과된 방식은 아래와 같다.

  1. 가방과 보석을 각각 용량과 무게 순으로 정렬한다.
  2. 가방을 하나씩 선택하여 해당 용량보다 작은 보석을 우선순위큐(가치 큰 것 우선)에 모두 넣어준다.
  3. 모두 넣으면 하나를 빼서 결과에 더한다. (해당 가방에 담을 수 있는 가장 큰 가치의 보석)

• 위 방식 역시 O(K * NlogN) 방식이라 좀 떨떠름하다..
  (가방이 30만개, 보석 30만개이고 가방 용량이 모두 최대라면 시간초과나지 않을까?)

소스 코드 (JAVA)

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

public class Main{
    static StringTokenizer st;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        PriorityQueue<int[]> pqueue = new PriorityQueue<int[]>((e1, e2) -> {
            return e2[1] - e1[1];
        });
        int[][] jewels = new int[N][2];
        int[] bags = new int[K];

        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine());
            jewels[n][0] = Integer.parseInt(st.nextToken());
            jewels[n][1] = Integer.parseInt(st.nextToken());
        }

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

        Arrays.sort(jewels, (e1, e2) -> {
            return e1[0] - e2[0];
        });
        Arrays.sort(bags);

        int index = 0;
        long answer = 0;

        for (int k = 0; k < K; k++) {
            int nowBag = bags[k];

            while (index < N) {
                if (jewels[index][0] <= nowBag) {
                    pqueue.add(jewels[index].clone());
                    index++;
                } else {
                    break;
                }
            }
            if(!pqueue.isEmpty()) {
                answer += pqueue.poll()[1];
            }
        }

        System.out.println(answer);
    }
}