[백준] 1092 배 - Java

 

 

 

문제 출저

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

1092번: 배

 

 

 

문제 풀이

크레인 n개가 주어진다. 

각 크레인은 들 수 있는 무게 제한이 주어진다.

박스 m개가 주어진다.

각 박스에는 무게가 있다. 

 

이 때, 크레인을 이용해서 박스를 옮길 때 전부 다 옮기는데 최소 시간을 구하는게 이 문제의 요구 사항 입니다. 

 

 

 

정렬과 구현으로 풀었습니다.

크레인, 박스를 내림차순 정렬하여 큰 숫자가 앞에 배치하도록 했습니다. 

그 후 큰 크레인이 큰 박스를 옮기도록 하여 시간을 구했습니다. 

이 때, 단순히 반복문을 돌리면 시간 초과가 발생합니다. 

 

큰 크레인이 옮기면서 박스를 탐색한 인덱스를 그대로 사용합니다.

즉, 큰 크레인이 선택한 박스의 인덱스부터 작은 크레인이 탐색하는 겁니다. 

이러한 방법으로 시간 초과를 해결했습니다. 

 

 

 

소스 코드

package baekjoon.backjoon10.day0110.day09;

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


/*
배
https://www.acmicpc.net/problem/1092
 */

public class B1092 {

    static int n;
    static List<Integer> cranes;

    static int m;
    static List<Integer> boxs;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        cranes = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            cranes.add(Integer.parseInt(st.nextToken()));
        }

        m = Integer.parseInt(br.readLine());
        boxs = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++) {
            boxs.add(Integer.parseInt(st.nextToken()));
        }

        // 내림차순 정렬
        Collections.sort(cranes, Collections.reverseOrder());
        Collections.sort(boxs, Collections.reverseOrder());


        // 크레인이 들 수 없는 박스가 있는 경우 -1 출력
        if(cranes.get(0) < boxs.get(0)) {
            System.out.println(-1);
            return;
        }

        int answer = 0; // 시간

        while(!boxs.isEmpty()) {

            int boxIndex = 0;

            for(int i = 0; i < n; i++) {
                int crane = cranes.get(i);

                while(true) {

                    if(boxIndex == boxs.size()) {
                        break;
                    }

                    if(crane >= boxs.get(boxIndex)) {
                        boxs.remove(boxIndex);
                        break;
                    }
                    boxIndex++;
                }
            }

            answer++;

        }

        System.out.println(answer);

    }

}