[백준]1202: 보석 도둑 - JAVA

[백준]1202: 보석 도둑

www.acmicpc.net/problem/1202

1202번: 보석 도둑

풀이

우선순위 큐를 사용한 문제로 굉장히 재미있게 느껴졌던 문제였다.

 

이 문제는 쉽게 생각하면 쉽게 풀 수는 있지만 시간복잡도에서 통과하기가 쉽지 않은 문제였다. 처음에는 우선순위큐를 사용하여 정렬을 통해 쉽게 풀 수 있을 것이라 생각했지만 역시나 시간 초과가 발생했다.

 

우선순위 큐를 두개를 만들어서 꺼내고 집어넣고를 반복하도록 코드를 짜니 정상 작동은 하지만 시간초과가 발생하였다. 더 효율적인 방법을 계속 고민해 보았고 아래와 같은 결론을 얻어 풀어낼 수 있었다.

 

논리적인 아이디어는 다음과 같다.

1. 보석을 arraylist로 입력받은 후 무게 순서대로 오름차순 정렬한다.
2. 가방에 담을 수 있는 최대 무게를 입력 받은 후 오름차순 정렬한다.
3. 가격 순서대로 내림차순 정렬을 하는 우선순위 큐를 생성한다.
4. 현재 가방이 담을 수 있는 최대 무게보다 작거나 같은 무게를 가진 보석을 우선순위 큐에 담아준다.
5. 우선순위 큐의 제일 첫 번째 값(가장 가격이 비싼 보석)을 꺼내어 더해준다.
6. 4 ~ 5를 반복해주면 된다.

 

코드

import java.util.*;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        int n = scan.nextInt();
        int k = scan.nextInt();
        
        ArrayList<Gem> list = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            int m = scan.nextInt();
            int v = scan.nextInt();
            list.add(new Gem(m, v));
        }
        Collections.sort(list, (o1, o2) -> o1.m - o2.m); //무게순 정렬
        
        int[] weight = new int[k];
        for(int i = 0; i < k; i++) {
            weight[i] = scan.nextInt();
        }
        Arrays.sort(weight);
        
        long total = 0;
        int listIdx = 0;
        PriorityQueue<Gem> pq = new PriorityQueue<>((o1, o2) -> o2.v - o1.v); //가격순 정렬
        for(int i = 0; i < k; i++) {
            while(listIdx < n && list.get(listIdx).m <= weight[i]) {
                Gem current = list.get(listIdx++);
                pq.add(new Gem(current.m, current.v));
            }
            if(!pq.isEmpty()) total += pq.poll().v;
        }
        System.out.println(total);
    }
    
    public static class Gem {
        int m;
        int v;
        
        public Gem(int m, int v) {
            this.m = m;
            this.v = v;
        }
    }
}