[알고리즘_풀이] 백준 backjoon 1202번, 보석 도둑

처음에 그냥 리스트에 넣고 정렬을 해줘서인지,,,,,, 시간초과가 났었던 문제.

 

정렬 시, 아주 빠른 속도를 보이는 우선순위큐를 이용해야했다.

시간복잡도 : O(logN)

 

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 보석 개수
        int K = sc.nextInt(); // 1개의 보석만을 담을 수 있는 가방

        Node[] jewelry = new Node[N]; // 보석의 정보를 담고 있는 Node 배열
        int[] max = new int[K];

        // 보석관련 정보를 N만큼 입력받는다.
        for(int i=0; i<N; i++){
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();

            jewelry[i] = new Node(n1, n2);
        }

        // 담을 수 있는 최대 무게
        for(int i=0; i<K; i++){
            max[i] = sc.nextInt();
        }

		// 이부분이 '그리디'스러운 방법이라고 생각한다.
        // 전부 오름차순 정렬
        Arrays.sort(max);
        // 무게순으로 오름차순 정렬
        Arrays.sort(jewelry);
        
        PriorityQueue<Integer> jewelryList = new PriorityQueue<>();

        long sum = 0;
        int j=0;
        // 가방에 담기위해서 가방의 개수만큼 돌린다.
        for(int i=0; i<K; i++){
            // 가방에 담을 수 있는 보석을 우선순위큐에 담는다.
            // 우선순위 큐 : 최대힙을 통해 구현된 자료구조.시간복잡도 : O(logN)으로, 일반 array나 List를 정렬하는 것보다 빠르다(성능이 좋다).
            // 기본값은 오름차순이지만, 내림차순이 필요한 경우 -를 붙여서 저장한 후, 꺼내쓸 때 절댓값을 출력하는 Math.abs(int n)이용
            while(j < N && jewelry[j].M <= max[i]) { //앞에서 담은것은 제외해야 하므로 while문과 j를 사용
                jewelryList.offer(-jewelry[j].V);
                j++;
            }
            // 제일 비싼 것이 가장 위에 있으므로, 그것만 뺴고 다음 max[i]로 넘어간다.
            if(!jewelryList.isEmpty()){
                sum += Math.abs(jewelryList.poll());
            }
        }
        System.out.println(sum);
    }

    static class Node implements Comparable<Node>{
        int M; // 무게
        int V; // 가격

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

        @Override
        public int compareTo(Node o) {
            return  this.M - o.M;
        }
    }
}