백준 1202번 - 보석 도둑 (java)

💡 문제 링크

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

 

💡 아이디어

지난번 Comparator 관련 글을 작성한 후 연습이 하고 싶어 관련 문제를 찾아서 풀었다.

온전히 스스로의 힘으로는 못하고 블로그를 참고했다.🥹

 

1번 아이디어 : 이중 for문

• 가방 리스트와 보석 리스트를 만들고 가방은 오름차순, 보석은 내림차순으로 정렬한다.
• 높은 가격의 보석부터 보석이 들어갈 수 있는 가방 중 가장 작은(무게 기준) 가방을 찾는다.
• 이중 for문을 활용하면 300,000 * 300,000 이므로 시간 초과가 뜰 것이다.

 

2번 아이디어 : 이분 탐색

• 가방 리스트와 보석 리스트를 만들고 가방은 오름차순, 보석은 내림차순으로 정렬한다.
• 높은 가격의 보석부터 보석이 들어갈 수 있는 가방 중 가장 작은(무게 기준) 가방을 찾는다.
• 여기까지는 1번 아이디어와 동일하다. 시간복잡도를 낮추기 위해 이분 탐색(lower-bound)를 활용하는 방안을 생각했다.
• 이분 탐색의 시간 복잡도는 O(logN) 이므로 300,000 * log300,000 = 약 160만 이므로 시간 초과가 나지 않을 것이라고 생각했다.
• 그러나 시간 초과가 떴다.

 

• 문제는 이미 사용한 가방을 사용할 수 없다는 점이었다.
• 보석이 들어갈 수 있는 가방 중 가장 작은 가방을 찾더라도 이미 보석이 담겨 있는 가방이면 그보다 큰 다른 가방을 찾아야 하는데 여기서 결국 터지는 것 같았다. (최악의 경우 O(N*K))
• 이 아이디어는 무게 기준으로 가장 작은 가방 탐색까지는 가능했지만, 이미 사용한 가방을 거르는 데 한계가 있다.
• boolean 변수를 쓰든, 리스트나 배열에서 값을 빼든 최악의 경우 O(N)이 O(K)에 곱해지기 때문이다.

 

3번 아이디어 : 우선순위 큐

• 우선순위 큐를 활용한다는 것은 블로그를 참고했다.
• 우선순위 큐는 값 추출(poll) 시간복잡도가 O(logN)이므로 이미 사용한 가방을 제거하고 정렬하는 시간복잡도가 작은 편이다.

알고리즘은 아래와 같다.

• 보석과 가방 모두 무게를 기준으로 오름차순 정렬한다.
• 우선순위 큐를 생성한다. (가격을 기준으로 내림차순 정렬)
• 가방 배열을 하나씩 보면서
  • 가방이 감당할 수 있는 무게보다 가벼운 보석을 모두 우선순위 큐에 넣는다.
  • poll한 보석의 가격을 정답 변수에 추가한다. (가장 비싼 보석이 가장 앞에 있을 것이므로)
• 위 2개 단계를 반복하되 새로운 가방에 대해 탐색할 때마다 보석을 처음부터 탐색하지는 않는다.
• 이미 넣은 보석은 다음 가방에 무조건 들어갈 수 있기 때문이다 (가방과 보석 모두 오름차순 되어 있다는 것을 기억하자)
• 이 때문에 시간복잡도도 이득을 보게 된다. O(K+NlogN)
  •  큐에 넣을 때마다 정렬되므로 N*logN이 더해지는 것

 

💡 코드

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;

public class BOJ_G2_1202_보석도둑_sol {
    public static int N, K;
    public static Jewel[] jewels;
    public static int[] bags;
    public static long maxV;

    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()); //가방 개수

        jewels = new Jewel[N];
        bags = new int[K];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            jewels[i] = new Jewel(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        for (int i = 0; i < K; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }
        //===================== 입력 완료

        //보석 무게를 기준으로 오름차순 정렬
        Arrays.sort(jewels, new Comparator<Jewel>() {
            @Override
            public int compare(Jewel o1, Jewel o2) {
                if (o1.M < o2.M) {
                    return -1;
                } else if (o1.M > o2.M) {
                    return 1;
                }
                return 0;
            }
        });

        //가방 무게를 기준으로 오름차순 정렬
        Arrays.sort(bags);

        //가격 기준으로 내림차순하는 우선순위 큐
        PriorityQueue<Jewel> queue = new PriorityQueue<>(new Comparator<Jewel>() {
            @Override
            public int compare(Jewel o1, Jewel o2) {
                if (o2.V < o1.V) {
                    return -1;
                } else if (o2.V > o1.V) {
                    return 1;
                }
                return 0; // o2.V == o1.V
            }
        });

        int index = 0;

        for (int i = 0; i < K; i++) {
            // 현재 가방에 넣을 수 있는 보석을 모두 큐에 넣음
            // 가방과 보석 모두 무게 기준으로 오름차순되어 있기 때문에 새로운 가방에 넣을 보석을 처음부터 탐색하지 않아도 됨
            // (index 변수가 for문 밖에서 선언된 이유)
            // 이미 넣은 보석은 다음 가방에 무조건 들어갈 수 있기 때문
            // 따라서 시간복잡도도 이득을 보게 됨 O(K*N)가 아닌 O(K+NlogN). 큐에 넣을 때마다 정렬되므로 N*logN이 더해짐
            while (index < N && bags[i] >= jewels[index].M) {
                queue.offer(jewels[index]);
                index++;
            }

            //현재 가방에 넣을 수 있는 보석 중 가장 비싼 보석을 꺼냄
            if (!queue.isEmpty()) {
                maxV += queue.poll().V;
            }
        }
        System.out.println(maxV);
    }

    public static class Jewel {
        int M; //무게
        int V; //가격

        Jewel(int M, int V) {
            this.M = M;
            this.V = V;
        }
    }
}