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

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

1202번: 보석 도둑

코드 :

import java.io.*;
import java.util.*;

class Jewel {
    int weight;
    int price;

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

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

        // 높은 가격순 정렬, 가격이 같다면 높은 무게 순으로 정렬
        PriorityQueue<Jewel> jewels = new PriorityQueue<>(new Comparator<Jewel>() {
            @Override
            public int compare(Jewel o1, Jewel o2) {
                if (o1.price == o2.price) {
                    return o2.weight - o1.weight;
                }
                return o2.price - o1.price;
            }
        });

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 총 보석 수
        int K = Integer.parseInt(st.nextToken()); // 가방 개수


        // 보석 우선순위큐에 넣기
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            jewels.offer(new Jewel(weight, price));
        }

        // <가방 무게 수용 - 가방 개수> 입력
        TreeMap<Integer, Integer> capacities = new TreeMap();
        for (int i = 0; i < K; i++) {
            int input = Integer.parseInt(br.readLine());
            capacities.put(input, capacities.getOrDefault(input, 0) + 1);
        }

        long answer = 0;

        while (!jewels.isEmpty()) {
            Jewel jewel = jewels.poll();

            // 빈 가방 없으면 종료
            if (capacities.isEmpty()) break;

            // 가장 큰 가방이 보석을 담지 못한다면 다음 해당 보석 포기
            if (capacities.lastKey() < jewel.weight) continue;

            // 보석 무게보다 큰 것 중 최솟값 구해서 사용처리(제거)
            int optimalBag = capacities.higherKey(jewel.weight - 1); //higher은 더 큰수부터 검색이므로, -1해서 자신까지 검색

            // 방금 사용한 가방이 마지막 가방이라면 Map에서 제거
            if (capacities.get(optimalBag) == 1) {
                capacities.remove(optimalBag);
            // 마지막 아니면 개수 - 1
            } else {
                capacities.put(optimalBag, capacities.get(optimalBag) - 1);
            }

            // 해당 보석 가방에 넣었으므로 가격 추가
            answer += jewel.price;
        }


        bw.write(answer+"");
        bw.flush();
        bw.close();
    }
}

풀이 :

어짜피 가방에는 보석 하나만 들어가니까, 비싼거부터 처리하는 방식으로 구현해보았다.

 

보석 객체를 만들어서 비싼 것부터(가격 내림차순) 정렬하고, 가격이 같다면 무거운 것부터(무게 내림차순) 정렬했다. 그 다음 정렬된 보석들을 (비싼것부터) 순회하면서 해당 보석을 넣을 수 있는 가방을 찾아서 처리하는 방식을 사용했다.

 

시간 복잡도가 O(n^2)인데, n은 최대 30만이라서 1초를 충족 못시키기때문에 TreeMap의 higherKey()메서드를 사용해서 가방들을 검색했다. 이 때 중복되는 가방의 무게가 있을 수 있기 때문에 TreeSet은 사용 불가능 하다.

 

주의할 함정 중 하나는 보석 가격의 총합은 최대 30만 * 100만이므로, int 범위를 넘어선다는 것이다. 이것때문에 풀이 자체가 틀린줄 알고 오래 고민했다.

 

다른 사람들의 코드는 아직 관찰중인데, 나랑 반대로 구현을 해서 당황했다. 나는 비싼 보석으로 검색하여 처리하는 방식이라면, 다른 사람들은 작은 가방에 대해 들어갈수있는 보석들 중 비싼 보석부터 처리하는 방식이다.

 

시간 복잡도 :

가방 개수를 배열로 만들어 모두 탐색 시, 시간은 가방 개수 최대 30만 * 보석의 개수 최대 30만 -> 9 * 10^10

 

시간초과를 방지하기 위해 Tree의 범위 탐색을 이용해보자. TreeSet을 사용하면 중복되는 가방 무게가 제거되므로 TreeMap을 사용해야한다.

 

TreeMap(), higherKey()

• 참고로 TreeMap은 key값을 기준으로 정렬시킨다. key-value쌍을 <가방의 수용가능 무게,  해당 무게인 가방의 개수>로 갱신했다.
• higherKey(K key)메서드는 입력한 값보다 큰 key값[가방 수용무게]들 중 가장 작은 것을 반환한다.
  • 즉, 입력한 값[보석의 무게]보다 큰 가방중 가장 작은 것을 골라 내부조각을 최소화하는 방법이다.

 

내일 더 찾아보고 마무리해야겠다.