[알고리즘 문제풀이] 백준 1092 배

오늘 푼 문제는 백준 1092- 배 입니다.

문제

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

예제

입력

3
6 8 9
5
2 5 2 4 7

출력

2

문제 풀이

가장 효율적으로 크레인을 사용하기 위해서 큰 제한 무게를 가진 크레인이 가벼운 박스를 옮기게 할당하고, 작은 제한 무게를 가진 크레인에 무거운 박스가 할당되어 옮기지 못하는 경우를 없애야 한다. 이 부분에 초점을 맞추고 문제를 풀었고, 간단한 문제이다 !

위의 문제를 다루기 위해서 크레인을 제한 무게가 큰 순서로 정렬하고, 박스도 무거운 순서로 정렬한다.

후에 가장 무거운 박스를 가장 제한 무게가 큰 크레인으로 옮길 수 있는지 체크한다. 만약 옮기지 못한다면 아예 옮길 수 없기에 모든 박스를 배로 옮길 수 없는 경우가 되므로 -1을 출력한다.

그렇지 않다면 박스를 다 옮길 때 까지 반복하며, 제한 무게가 큰 크레인부터 순차적으로, 무거운 순서로 정렬된 박스를 할당한다.

이 때, 옮길 수 없는 박스에 대해서는 그냥 두고 다음 박스로 넘어가는 방식으로 구현한다. 그러기 위해서 박스를 순회하기 위한 index 변수를 따로 사용하며 증가시켜주고, 크레인을 순회하는 for문의 변수는 감소하여 해당 크레인에 대해서 다시 새로운 박스를 할당할 수 있게끔 해주었다.

박스를 할당한다는 것은 배로 옮길 수 있는 것이므로 리스트에서 박스를 제거해주었고, 세 개의 트레인이 동시에 동작한다고 하였으므로 트레인에 대해서 1회 반복이 완료될 때마다 시간을 증가시켜주었다.

최종적으로 박스가 다 옮겨지면, 즉 박스 리스트가 텅 비면 그 때의 시간을 반환하는 방식이다.

코드

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

public class Main {
    static class Solution{
        ArrayList<Integer> limits;
        ArrayList<Integer> weights;
        Solution(ArrayList<Integer> limits, ArrayList<Integer> weights){
            this.limits = limits;
            this.weights = weights;
        }
        int solution(){
            int result = 0;
            int index;
            limits.sort(Collections.reverseOrder());
            weights.sort(Comparator.reverseOrder());
            if(limits.get(0) < weights.get(0)) return -1;
            while(!weights.isEmpty()){
                index = 0;
                for(int i=0; i<limits.size(); i++){
                    if(index >= weights.size()) break;
                    if(limits.get(i) >= weights.get(index)) weights.remove(index);
                    else{
                        index++;
                        i--;
                    }
                }
                result++;
            }
            return result;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // reader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // writer
        StringTokenizer st; // tokenizer

        int n = Integer.parseInt(br.readLine());
        ArrayList<Integer> limits = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            limits.add(Integer.parseInt(st.nextToken()));
        }
        int m = Integer.parseInt(br.readLine());
        ArrayList<Integer> weights = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++){
            weights.add(Integer.parseInt(st.nextToken()));
        }
        Solution solution = new Solution(limits, weights);
        bw.write(String.valueOf(solution.solution()));

        bw.write( "\n"); // for return value
        bw.flush(); // flush
        bw.close(); // close
        br.close(); // close
    }
}