BOJ 1202 - 보석 도둑(Java)

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

1202번: 보석 도둑

 

풀이

완전 탐색으로 풀 경우 보석의 개수 N(1 ~ 300,000), 가방의 개수 M(0 ~ 100,000,000)으로 O(N*M)의 시간 복잡도를 가짐, 안될 거라 생각하고 풀어봤지만 역시나 시간초과 발생

 

* 시간 복잡도를 줄여야하며 우선순위 큐를 이용하여 품

 

우선 순위 큐를 이용한 풀이

- 가방에 대해서는 for문을 이용하여 탐색

- 현재 가방의 무게 용량 이하로만 우선순위에 담아, 가장 가치가 큰 보석을 선택

    - 우선순위 큐는 보석 가치에 대해 내림차순으로 정렬되야함

    - 현재 가방에 대해 보석을 탐색 할 때는 이전 탐색이 끝난 위치의 전은 확인할 필요가 없음 

        -> 보석을 무게 기준 오름차순으로 정렬했기 때문에

    

* 이러한 방법으로 풀 경우 O(N + M)의 시간 복잡도로 풀이 가능

* 자료형 선언을 신경 쓰지 못해 계속 틀린 결과가 나왔음

    - 훔칠 수 있는 보석 가격의 합의 최대값 = K(300,000) x V(0 ~ 100,000,000)으로 long형으로 선언해야함

 

 

전체 코드

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

public class Main {

    static int N, K;
    static Integer[] bags;
    static jewel[] jewels;

    static class jewel {
        int M, V;

        jewel(int M, int V) {
            this.M = M;
            this.V = V;
        }
    }

    public static void main(String[] args) 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());

        jewels = new jewel[N];
        bags = new Integer[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());
            jewels[i] = new jewel(M, V);
        }
        // 보석 리스트를 무게 오름차순으로 정렬
        Arrays.sort(jewels, new Comparator<jewel>() {
            @Override
            public int compare(jewel o1, jewel o2) {
                return o1.M - o2.M;
            }
        });

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            bags[i] = Integer.parseInt(st.nextToken());
        }
        // 가방을 용량 오름차순으로 정렬
        Arrays.sort(bags);

        long ans = 0;
		
        // 우선순위 큐 - 가치 내림차순으로 
        PriorityQueue<jewel> pq = new PriorityQueue<>((o1, o2) -> o2.V - o1.V);
        int jewelIdx = 0;
        for (int i = 0; i < K; i++) {
            while (jewelIdx < N && jewels[jewelIdx].M <= bags[i]) {
                pq.add(jewels[jewelIdx++]);
            }
            if (!pq.isEmpty()) ans += pq.poll().V;
        }
        System.out.println(ans);
    }
}