[PS] BOJ1202 보석도둑 ( greedy ) With JAVA

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

1202번: 보석 도둑

 

 

◎문제풀이

 

보석이 N개 있고 가방이 K개 있을 때, 가방에 보석을 담을 수 있는 최대가격을 구하는 문제이다. ( 단, 가방 안에는 하나의 보석만 담을 수 있다. )

 

처음에는 N개의 보석을 내림차순으로 정렬하고 가방K개를 오름차순을 정렬하여, 보석의 무게에 맞는 가방을 탐색하려고 했다. 그러나 이는 시간복잡도가 O(N*K)이고 N과 K는 1 ≤ N, K ≤ 300,000이므로, 시간제한 1초를 넘어설 것이라 판단했다. 별생각을 다해보았지만 시간제한 안에 보석을 담을 가방을 탐색하는 방법이 떠오르지 않아, 풀이를 찾아보았는데 보석이 아닌 가방에 초점을 맞추어야 풀리는 문제였다. 

 

최대가격이 나오려면 가방 K개에 모두 보석이 담겨야 한다. 보석 N개는 가방의 개수가 적으면 일부가 안 담겨진다. 그러므로 가방이 기준이 되어야 한다. 보석에 맞는 가방을 탐색하는 것이 아니라 가방에 맞는 보석을 탐색해야 한다.

 

 

 

 

 

가방과 보석을 무게를 기준으로 오름차순으로 정렬한다.  가방 50g에는 30g과 40g이 들어갈 수 있다.

 

 

 

 

가격이 높은 보석은 30g가방이니 가방50g에는 30g보석을 넣는다. 

 

 

 

 

가방 65g은 보석 40g만 넣을 수 있으니 40g을 넣는다. 

 

 

 

 

가방 80g에는 70g과 75g을 넣을 수 있다. 가격이 높은 75g을 넣어준다. 

 

 

 

 

가방 200g은 70g과 100g을 넣을 수 있다. 가격이 높은 70g을 넣는다. 

 

 

 

 

 

이를 코드로 구현하려면 우선순위 큐가 필요하다.

 

우선순위 큐는 보석을 담는 큐로, 현재 가방에 담길 수 있는 무게의 보석들을 저장한다. 그리고 가격을 우선순위로 하여, 가격이 높은 순서대로 저장한다. 그러므로 가방에 들어갈 수 있는 보석 중 가격이 가장 높은 보석을 POP하여 가방에 넣을 수 있는 것이다. 이를 코드로 확인해 보자. 

 

◎코드

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

//BOJ1202 보석도둑
public class Main {

    static StringTokenizer st;
    static Jew[] jews;
    static int[] bags;
    static int k;
    static int n;

    static class Jew {
        int m; //무게
        int v; //가격

        public Jew(int m, int v) {
            this.m = m; 
            this.v = v;
        }

    }
    public static void main(String[] args) throws IOException {
        input();
        solution();
    }


    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        jews = new Jew[n];
        bags = new int[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());
            jews[i] = new Jew(m,v);
        }
		//가방 입력받기
        for(int j=0;j<k;j++){
            st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken());
            bags[j]= c;
        }
		// 보석을 무게로 오름차순 정렬하기
        Arrays.sort(jews, new Comparator<Jew>() {
            @Override
            public int compare(Jew o1, Jew o2) {
                if(o1.m==o2.m) return o2.v - o1.v; // 무게가 같으면 가격으로 내림차순 정렬
                return o1.m - o2.m; // 무게로 오름차순 정렬
            }
        });
		// 가방을 무게로 오름차순 정렬하기
        Arrays.sort(bags); 
    }

    public static void solution(){
    	// 우선순위 큐 생성
        PriorityQueue<Jew> pq = new PriorityQueue<>((j1,j2)-> j2.v - j1.v); // 가격을 기준으로 내림차순 정렬
        long ans = 0;
        int j =0;
        for(int i =0; i<k; i++){ // 가방을 기준으로 탐색
            while(j<n&&jews[j].m<=bags[i]){ // 현재 가방보다 무게가 낮은 보석들을 차례로 우선순위큐에 넣기
                pq.offer(jews[j++]);
            }
            if(!pq.isEmpty()) ans += pq.poll().v; // 우선순위 큐에 저장된 보석 중 가격이 가장 높은 보석 POP
        }
        System.out.println(ans);
    }

}

 

 

시간복잡도는 O(N+K)이므로 시간제한에 걸리지 않는다.