[자바] 1202 보석 도둑

자바 / 골2 / 그리디 알고리즘 / 자료구조 / 우선순위 큐

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

 

우선, C에서는 pair를 우선순위 큐의 요소로 넣어주면 쉽게 풀 수 있는 코드이지만, 자바에는 pair의 개념이 없어서 직접 구조체를 만들어줘야 했다. 이 과정에서 학습한 자바에서의 구조체 선언, 생성과 초기화에 대해서는 추후 다른 게시글로 다루도록 한다.

또한 여타 다른 그리디 문제들과 마찬가지로... 시간 초과와의 힘든 싸움이었다.

 

class Jewelry{
    int weight;
    int price;

    public Jewelry(int weight, int price) {
        this.weight = weight;
        this.price = price;
    }
}

먼저, Jewelry라는 구조체를 선언해줬다. 해당 구조체를 초기화하는 생성자도 만들어줬다.

 

 

처음 접근한 방식은, price를 기준으로 보석의 우선순위 큐를 만들고 가방에 들어가는 무게를 기준으로 오름차순 정리를 한 후, 각 bag의 무게보다 작은 것이 큐에서 나오기만 하면 그것이 해당 가방에 넣을 수 있는 최적의 해이므로, 그 보석을 채택한다.

하지만 이렇게 하면 가방과 보석에 대해 중복해서 도는 경우가 생겨 최대 300000*300000번을 돌게 된다. 즉, 시간초과가 난다.

 

초기 코드

        while(!pq.isEmpty()) {
            Jewelry tmp = pq.poll();
            for(int i = 0; i < K; i++) {
                if (filledbag[i] || tmp.weight > bag[i]) {
                    continue;
                }
                else {
                    ans += tmp.price;
                    filledbag[i] = true;
                    break;
                }
            }
        }

 

그래서 이렇게 하면 안되고, 최대 무게가 더 작은 가방에 들어갈 수 있는 무게의 보석은 다음 무게의 가방에도 들어갈 수 있다는 점을 이용하여 코드를 다시 짰다. (지피티의 힘을 빌려 얻어낸 효율적인 알고리즘이다)

 

<알고리즘>

Jewelry 구조체를 요소로 갖는 구조체 배열 jewelries를 선언하여, 해당 배열을 "무게에 대해" 오름차순으로 정렬했다.

       	// 보석 구조체 배열에 값 넣기
        for(int i = 0; i < N; i++) {
            s = br.readLine();
            st = new StringTokenizer(s);
            int weight = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            jewelries[i] = new Jewelry(weight, price);
        }
		
        // 가방 배열에 값 넣기
        for(int i = 0; i < K; i++) {
            bag[i] = Integer.parseInt(br.readLine());
        }

		// 보석 구조체 배열을 무게를 기준으로 오름차순으로 정리
        Arrays.sort(jewelries, (j1, j2) -> Integer.compare(j1.weight, j2.weight));
        // 가방 배열을 무게를 기준으로 오름차순으로 정리
        Arrays.sort(bag);

그 후 각 가방을 오름차순으로 탐색하며, 해당 가방에 들어갈 수 있는 무게의 보석을 "가격을 기준으로 내림차순으로" 우선순위 큐에 넣어주었다.

이렇게 하면 각 가방에 대해 모든 보석을 탐색하는 게 아닌, 앞선 가방에 들어갈 수 있는 보석은 다음 가방에도 들어갈 수 있다는 점을 반영해주었기 때문에(큐에 그대로 남아 있음) 중복해서 확인하는 경우를 막을 수 있다.

        PriorityQueue<Jewelry> pq = new PriorityQueue<>((j1, j2) -> Integer.compare(j2.price, j1.price));

        int idx = 0; //보석 구조체 배열은, 가방의 하위에서 이중 반복문이 도는 게 아니라 두 인덱스가 아예 따로 돌아야 함
        for(int i = 0; i < K; i++) {
            while (idx < N && jewelries[idx].weight <= bag[i]) {
                pq.add(jewelries[idx]);
                idx++;
            }
            if (!pq.isEmpty()) {
                ans += pq.poll().price;
            }
        }

 

다음은 전체 코드이다.

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N, K;
        long ans = 0;
        
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        Jewelry[] jewelries = new Jewelry[N];
        int [] bag = new int[K];

        for(int i = 0; i < N; i++) {
            s = br.readLine();
            st = new StringTokenizer(s);
            int weight = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            jewelries[i] = new Jewelry(weight, price);
        }

        for(int i = 0; i < K; i++) {
            bag[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(jewelries, (j1, j2) -> Integer.compare(j1.weight, j2.weight));
        Arrays.sort(bag);

        PriorityQueue<Jewelry> pq = new PriorityQueue<>((j1, j2) -> Integer.compare(j2.price, j1.price));

        int idx = 0;
        for(int i = 0; i < K; i++) {
            while (idx < N && jewelries[idx].weight <= bag[i]) {
                pq.add(jewelries[idx]);
                idx++;
            }
            if (!pq.isEmpty()) {
                ans += pq.poll().price;
            }
        }

        System.out.println(ans);
    }

}

class Jewelry{
    int weight;
    int price;

    public Jewelry(int weight, int price) {
        this.weight = weight;
        this.price = price;
    }
}