정렬_1202_보석 도둑

오늘도 정렬로 분류되는 알고리즘 문제를 풀어보도록 하자. 
문제의 난이도가 골드 2로 올라와서 그런지 따져야 할 조건도 많고, 풀이도 떠올리기가 간단하지는 않았다. 
기본 베이스는 정렬과 그리디 알고리즘이지만, 이번 문제는 우선순위 큐라는 자료구조를 적당히 잘 사용해서 풀어야 한다.

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

1202번: 보석 도둑

 

1. 문제 분석

• 보석의 수 N과 가방의 수 K의 최댓값이 삼십만개 이다. 각 보석의 최대 가치가 백만인점을 고려하면 최악의 경우 정답으로 나올 수 있는 최대 가격은 3천억이 되기 때문에 정답의 자료형은 long을 사용한다. 
• 객체 정렬을 사용해야 할 것 같다. Comparable or Comparator
• 각 가방에는 하나의 보석만을 넣을 수 있기 때문에 우선순위 큐를 사용해 최대 가치를 찾아야 할 것 같다.

 

2. 잘못된 접근

• 우선순위 큐 내부에서 우선순위를 결정할 정렬 기준을 지정하지 않고 그냥 모든 보석을 때려 넣었다. 
  • 큐 내부에서 정렬이 되지 않아서 우선순위큐를 사용하는 의미가 없다. 그냥 넣은 순서대로 나올 뿐이다.
• 가방의 무게를 맵의 키값에 매핑시켰다. 
• 각 보석마다 반복을 돌면서 현재 우선순위 큐에서 뽑은 보석의 무게보다 큰 가방을 찾은 리스트를 정렬한다.
  • 조건을 잘 보면 보석과 가방간의 부등호가 없다. 보석이 가방보다 적을 수도 많을 수도 있다는 것이다.
  • 즉, NPE가 발생할 수도 있다. 
  • 최악의 경우 보석 개수 * 가방 개수 -> 9백억 번의 연산이 일어나기 때문에 시간초과가 발생한다. 
• 찾은 리스트 중 가장 가벼운 가방의 무게(key)값에 보석의 가치(value)를 매핑한다.
• 반복이 끝난 후에 map의 value값들을 모두 더한다.

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Queue<Jewel> q = new PriorityQueue<>(N);
        HashMap<Integer, Integer> weightMap = new HashMap<>(K);
        q.stream().sorted();

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

        for(int i=0; i<K; i++) {weightMap.put(Integer.parseInt(br.readLine()), 0);}

        for(int i=0; i<N; i++){
            Jewel poll = q.poll();
            List<Integer> collect = weightMap.keySet().stream().filter(v -> v > poll.weight).sorted().collect(Collectors.toList());//뽑은 보석의 무게보다 큰 놈들을 고른 후 오름 차순 정렬한 리스트
            if(collect.size() >0 && weightMap.get(collect.get(0)) < poll.price) {
                weightMap.put(collect.get(0), (int) poll.price);
            }

        }

        int answer = weightMap.values().stream().mapToInt(v -> v).sum();
        System.out.println(answer);

 

위의 문제점을 기준으로 접근을 다시 해보면 아래와 같이 정리할 수 있겠다.

1. 보석보단 가방에 넣어진 가치가 계산되기 때문에 반복의 기준은 가방이 되어야 한다.
2. 각 가방마다 하나의 보석을 넣을 수 있는데 보석을 넣을때는 최대 가치의 보석을 넣어야 하기 때문에 보석이 우선순위 큐에서 정렬될 기준을 정해야 한다. 
3. 가벼운 무게부터 비교해 가면서 가치가 큰 것부터 나올 수 있도록 하자.

 

3. 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

class Jewel{
    int weight;
    int price;

    public Jewel(int weight, int price) {
        this.weight = weight;
        this.price = price;
    }
}
public class _1202 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Queue<Jewel> valuableJewel = new PriorityQueue<>((o1, o2) -> o2.price - o1.price);

        List<Jewel> jewelList = new ArrayList<>(N);
        List<Integer> bagList = new ArrayList<>(K);

        //보석 초기화
        for(int n=0; n<N; n++){
            st = new StringTokenizer(br.readLine());
            jewelList.add(new Jewel(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        //가방 초기화
        for(int k=0; k<K; k++) {bagList.add(Integer.parseInt(br.readLine()));}

        //작은 가방에 넣을 수 있는 최대 가치의 보석을 넣어야 한다. 
        //가벼운 보석부터 오름차순으로 정렬
        Collections.sort(jewelList, (o1, o2) ->  o1.weight - o2.weight);
        
        //가방이 가벼운 것부터 오름차순 정렬
        Collections.sort(bagList);

		//보석의 인덱스
        int idx = 0;
        long answer = 0L;

		//보석이 가방보다 많을수도 있고 적을 수도 있음. 보석을 담을 가방이 기준이 되어야 한다.
        for(int k=0; k<K; k++){
            int nowBagSize = bagList.get(k);

            //현재 가방에 """들어갈 수 있는 보석"""을 모두 우선순위 큐에 때려 넣는다.
            while(idx < N){
                if(jewelList.get(idx).weight <= nowBagSize){
                    valuableJewel.add(new Jewel(jewelList.get(idx).weight,jewelList.get(idx).price));
                    idx++;
                }else break;
            }
            
            /**
            *  각 가방에 가장 가치가 큰 하나의 보석을 넣음 -> 한 반복당 하나의 보석 넣기
            *  이전 반복에서 등록된 보석이 다음 반복에서 나오는 가방에는 무조건 들어갈 수 있다. 
            *  왜냐하면 뒤에 나오는 가방은 수용 가능한 최대 무게가 더 크기 때문이다.
            *  따라서 가치가 더 큰 것을 넣으면 되는 것.
            */ 
            if(!valuableJewel.isEmpty()) answer += valuableJewel.poll().price;
        }
        System.out.println(answer);
    }
}