[백준] 1202번 보석 도둑

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

 

최근 본 기업 코테에서 상당히 유사한 문제가 출제 되었다. 

결국... 맞추진 못했지만... 다시 복기 하기 위해 풀어보았다. 

기업 코테와 다른 점은.. 기억하기론 기업 코테에서는 가방에 물건을 여러개 넣어도 됐었다. (->이건 어떻게 풀어야했을까..?)

 

해당 문제에서는 하나만 가방에 넣을 수 있다. 

 

따라서 최대 무게가 작은 가방부터 순서대로 탐색을 시작하여, 가방에 최대 가치가 있는 보석을 넣는 방식으로 구현하여 풀 수 있다.

 

이를 위해, 

1. 보석도 무게 순으로 오름차순 정렬을 한다. 

2. 가방 최대 무게를 받아서, 오름차순으로 정렬을 한다. 

3. 가방 정렬한 순서대로, 최대 무게 내에 가장 가치 높은 물건을 담는다. (우선순위 큐 사용)

 

++) 계속하여 런타임 에러가 났다. 원인은... pq가 비어있는지 확인하고 poll을 했어야하는데 비어있는지 확인을 안했다. 앞으로 큐.poll 할 때에는 비어있는지 꼭 체크를 해야겠다. 

++) 해당 문제에서 입력 값 중에 오버플로우가 날 여지가 있는 입력 값이 있다. 따라서 오버플로우가 날 수 있는 변수의 경우, long으로 선언해준다. 

 

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

public class codingtest {
    static int N, K;

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

        ArrayList<int[]> list = new ArrayList<>(); // 보석 정보 담을 리스트.

        for (int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            list.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())}); // 보석 정보 담기(무게, 가격)
        }

        Collections.sort(list, (o1, o2) -> o1[0] - o2[0]); //무게별 오름차순

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

        Arrays.sort(bag); // 가방 오름차순

        PriorityQueue<int[]> pq = new PriorityQueue<>(((o1, o2) -> o2[1] - o1[1]));

        int search_index = 0;
        long sum_value = 0; // K*최대무게이면 오버플로우날 수 있기때문에 long

        for (int i = 0 ; i < K; i++){
            for (int j = search_index; j < N; j++){ // 한번 탐색했으면 다음엔 탐색 안하도록 탐색 인덱스 따로 둠.
                // 무게가 K의 최대무게보다 크면 break 하기 (더이상 못 담음)
                int jewel[] = list.get(j);
                int weight = jewel[0];

                // 만약 무게 > K의 최대무게이면 더 이상 탐색하지 않도록 break 하기

                // 무게 <= K의 최대무게 (즉, 가방에 담을 수 있다면) 큐에 담고, 인덱스 ++ 하기
                if (weight <= bag[i]){
                    pq.add(jewel);
                    search_index++;
                } else if (weight > bag[i]){ // list는 애초에 무게순으로 정렬했기 때문에 순서대로 비교함.
                    break;
                }
            }

            if (!pq.isEmpty()){
                int first[] = pq.poll(); // 가방에 넣을 수 있는 무게 중 가장 가치 높은 것
                sum_value += first[1];
                
            }
        }

        System.out.println(sum_value);
    }
}