[BOJ] 1202 : 보석 도둑(Java)

문제 링크

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

1202번: 보석 도둑

---

💡 풀이

문제 풀이의 큰 틀은 우선 입력 받는 보석 [M, V]를 무게(M) 기준으로 오름차순 정렬하여 리스트에 저장합니다. 이때, 무게가 같다면, 가격을 기준으로 내림차순 정렬합니다. 

입력 받는 가방 또한, 가방에 담을 수 있는 최대 무게를 기준으로 오름차순 정렬합니다. 그 뒤 탐색을 시작합니다.

탐색은 가방을 기준으로 진행됩니다. 

가방과 보석이 오름차순으로 정렬되어 있기 때문에 순차적으로 탐색을 진행해 나아갑니다. 이때, 특정 가방에 담을 수 있는 무게보다 작은 보석의 가격을 모두 우선순위 큐에 담아줍니다. 가방 한 개에 대한 탐색을 마치면 우선순위 큐가 비워져 있지 않다면 우선순위 큐의 맨 첫 요소의 가격을 정답 변수에 더해줍니다. 이런 식으로 진행한다면 한 번 탐색한 보석은 탐색하지 않기 때문에 시간을 줄일 수 있습니다.

 

보석 클래스

우선, 보석 정보를 저장할 Jewel 클래스를 정의합니다.

static class Jewel {
    int weight;
    int value;

    public Jewel(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }
}

보석 정렬

다음은 입력 값으로 부터 보석을 정렬하는 부분입니다.

int M, V;
list = new ArrayList<>();
for (int i = 0; i < N; i++) {
    st = new StringTokenizer(br.readLine());
    M = Integer.parseInt(st.nextToken());
    V = Integer.parseInt(st.nextToken());
    list.add(new Jewel(M, V));
}
Collections.sort(list, ((o1, o2) -> {
    if (o1.weight == o2.weight) {
        return o2.value - o1.value;
    }
    return o1.weight - o2.weight;
}));

Collections로 List를 정렬할 때, 두 번째 파라미터에 Comparator 인터페이스의 구현을 통해 정렬 기준을 설정 할 수 있습니다. 위 코드를 살펴보면, 무게가 같을 경우는 가격을 기준으로 내림차순 정렬을 하고 무게가 같지 않을 경우, 무게를 기준으로 오름차순으로 정렬하는 인터페이스 구현입니다. 

가방 정렬

다음은 가방에 담을 수 있는 무게를 입력 받고 정렬하는 과정입니다. 

 // 가방 정보 입력
bags = new int[K];
for (int i = 0; i < K; i++) {
    bags[i] = Integer.parseInt(br.readLine());
}
// 가방의 무게를 기준으로 오름차순 정렬
Arrays.sort(bags);

탐색

이제 위의 정보를 가지고 가방을 채워 나아가며 탐색을 진행합니다. 

// 가방 채워 나가기
long result = 0;
// 우선 순위 큐에는 가치를 기준으로 내림차순으로 정렬
pq = new PriorityQueue<>(((o1, o2) -> o2 - o1));
for (int i = 0, j = 0; i < K; i++) {
    while (j < N && list.get(j).weight <= bags[i]) {
        pq.offer(list.get(j).value);
        j++;
    }

    if (!pq.isEmpty()) {
        result += pq.poll();
    }
}

정답 값의 최댓값은 300,000 * 1,000,000 이기 때문에 int 값을 넘어가 long으로 선언해줍니다. 

그리고 여기서 사용되는 우선순위 큐의 정렬 기준은 보석의 가격이 높은 순서, 즉, 내림차순으로 정렬해줍니다. 가방 무게 순으로 탐색을 진행하며, 가방의 무게보다 작은 보석의 가격을 우선 순위 큐에 넣어주고 가방에 대한 탐색이 끝나면, 맨 앞요소를 가져와 더해주는 방식입니다. 

 

전체 코드

전체적인 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Q1202 {
    static int N, K;
    static int[] bags;
    static ArrayList<Jewel> list;
    static PriorityQueue<Integer> pq;

    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());

        // 보석 정보 입력
        int M, V;
        list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            V = Integer.parseInt(st.nextToken());
            list.add(new Jewel(M, V));
        }
        Collections.sort(list, ((o1, o2) -> {
            if (o1.weight == o2.weight) {
                return o2.value - o1.value;
            }
            return o1.weight - o2.weight;
        }));

        // 가방 정보 입력
        bags = new int[K];
        for (int i = 0; i < K; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }
        // 가방의 무게를 기준으로 오름차순 정렬
        Arrays.sort(bags);

        // 가방 채워 나가기
        long result = 0;
        // 우선 순위 큐에는 가치를 기준으로 내림차순으로 정렬
        pq = new PriorityQueue<>(((o1, o2) -> o2 - o1));
        for (int i = 0, j = 0; i < K; i++) {
            while (j < N && list.get(j).weight <= bags[i]) {
                pq.offer(list.get(j).value);
                j++;
            }

            if (!pq.isEmpty()) {
                result += pq.poll();
            }
        }

        System.out.println(result);
    }

    static class Jewel {
        int weight;
        int value;

        public Jewel(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }
}