[백준] 1202 보석도둑 [java]

문제

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

풀이 방법

무게와 가치가 다른 보석을 한 가방에 담는 대표적인 그리디 알고리즘 문제를 살짝 변형한 문제이다.
다른 점은, 무게가 정해진 가방에 하나의 보석만 담을 수 있고, 여러개의 보석을 담을 수 있다는 점이다.
그래도 그리디 알고리즘이라는 것은 변함이 없다. 가방에 담을 보석을 고를 때, 최선의 선택을 하여 가방에 보석을 최대한의 가치로 담으면 되기 때문이다.


1. 보석을 무게 기준으로 오름차순 정렬한다.
2. 가방을 무게 기준으로 오름차순 정렬한다.
3. 가방을 탐색하면서 현재 가방에 들어갈 수 있는 (가방 최대 무게보다 작거나 같은) 보석을 우선순위 큐에 넣는다. (우선순위 큐는 가치가 높은 것이 peek에 오도록 한다.)
4. 우선순위큐에서 보석을 꺼내 가방에 넣는다. (현재 가방에 넣을 수 있는 보석 중 가장 가치가 큰 것)
5. 모든 가방이 꽉 차거나 보석을 모두 넣으면 종료한다.

핵심 코드

• 컬렉션을 일정한 기준으로 정렬

public static class Jewel{
        int weight;
        int value;
//
        public Jewel(int weight, int value){
            this.weight = weight;
            this.value = value;
        }
    }
//    
publc Main{
	psvm(){
    	List<Jewel> jewels = new ArrayList<>();
        Collections.sort(jewels, (o1, o2) -> o1.weight - o2.weight);	//무게 기준 오름차순 정렬
}

• 우선순위 큐의 기준 지정

public static class Jewel{
        int weight;
        int value;
//
        public Jewel(int weight, int value){
            this.weight = weight;
            this.value = value;
        }
    }
//    
publc Main{
	psvm(){
    	// value가 큰 것을 부모로 지정
    	PriorityQueue<Jewel> priorityQueue = new PriorityQueue<>((o1, o2) -> o2.value - o1.value);
    }
}

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
//
public class Main {
//
    public static class Jewel{
        int weight;
        int value;
//
        public Jewel(int weight, int value){
            this.weight = weight;
            this.value = value;
        }
    }
//
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int jewelInfo = Integer.parseInt(stringTokenizer.nextToken());
        int bagInfo = Integer.parseInt(stringTokenizer.nextToken());
        List<Jewel> jewelList = new ArrayList<>();
        for(int i = 0; i < jewelInfo; i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int weight = Integer.parseInt(stringTokenizer.nextToken());
            int value = Integer.parseInt(stringTokenizer.nextToken());
            jewelList.add(new Jewel(weight, value));
        }
        int[] bag = new int[bagInfo];
        for(int i = 0; i < bagInfo; i++){
            bag[i] = Integer.parseInt(bufferedReader.readLine());
        }
        Arrays.sort(bag);       //가방 오름차순 정렬
        Collections.sort(jewelList, (o1, o2) -> o1.weight - o2.weight);     //보석 무게 기준 오름차순 정렬
//
        // 보석 가치 내림차순 정렬
        PriorityQueue<Jewel> priorityQueue = new PriorityQueue<>((o1, o2) -> o2.value - o1.value);
        long ans = 0;
//
        int jewelIdx = 0;
        for(int i = 0; i < bagInfo; i++){
            while(jewelIdx < jewelInfo && jewelList.get(jewelIdx).weight <= bag[i]){
                priorityQueue.add(jewelList.get(jewelIdx++));
            }
            if(!priorityQueue.isEmpty()){
                ans += priorityQueue.poll().value;
            }
        }
//
        System.out.println(ans);
    }
}

느낀점

Jewel.class처럼 정보가 여러개 담겨있는 데이터를 다룰 때, 2차원배열로 하지 않고, 클래스를 만들어 객체로 다루는 것이 더 좋은 것 같다.