[JAVA] 백준 1092 배_최소힙

 

문제 : 
https://www.acmicpc.net/problem/1092

 

 

접근 : 

 

  - Case 1 : 만약 제일 무거운 박스가 트레인 중 가장 높은 허용 무게를 초과하는 경우, -1 반환

 

  - Case 2 : 박스의 무게가 현재 트레인의 허용 무게 이하인 경우, 박스를 남은 트레인을 고려하여 박스를 나눠 분담

 

  - Case 3 : 박스의 무게가 현재 트레인의 허용 무게 보다 높은 경우, 남은 트레인의 수를 고려하여 골고루 분담하는 갯수를 계산

 

  - Case 4 : 만약 트레인이 마지막 트레인이라면, 남은 모든 박스를 이동 

 

 

 

 

코드 구현 : 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

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

        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> crane = new PriorityQueue<>();

        String[] inputs = br.readLine().split(" ");
        int crane_max = 0;
        int temp = 0;
        for(int i = 0 ; i < n ; i++){
            temp = Integer.parseInt(inputs[i]);
            crane.offer(temp);
            crane_max = Math.max(crane_max, temp);
        }

        int m = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> box = new PriorityQueue<>();

        int box_max = 0 ;
        inputs = br.readLine().split(" ");

        for(int i = 0 ; i < m ; i++){
            temp =  Integer.parseInt(inputs[i]);
            box.offer(temp);
            box_max = Math.max(box_max, temp);
        }
        // 상자를 전부 옮기지 못하는 경우
        if(crane_max < box_max){
            System.out.println(-1);
            return;
        }
        int ans = 0;
        int res = 0;
        int size = Math.max(ans, box.size()/crane.size() + ((box.size() % crane.size() == 0) ? 0 : 1));

        while (!box.isEmpty()){
            // 마지막 크레인인 경우 남은 박스 넣기
            if(crane.size() == 1){
                ans = Math.max(ans, box.size());
                break;
            }
            // 상자를 넣을 수 있는 경우
            if(crane.peek() >= box.peek() && res < size) {
                ans = Math.max(ans, ++res);
                box.poll();
                continue;
            }

            // 상자에 넣을 수 없는 경우
            crane.poll();
            size = Math.max(ans, box.size()/crane.size() + ((box.size() % crane.size() == 0) ? 0 : 1));
            res = 0;
        }
        System.out.println(ans);
    }
}