백준 1092번 - 배

문제

백준 1092번 - 배

아이디어

• 그리디하게 무거운 무게를 들 수 있는 크레인이 무거운 박스부터 옮길 수 있도록 한다.
• 크레인 무게 제한과 박스의 무게를 정렬한다. 만약 가장 무거운 박스의 무게가 가장 무거운 무게를 들 수 있는 크레인의 무게 제한보다 무거우면 절대 모든 박스를 옮길 수 없다.
• M개의 박스를 모두 옮길 때까지 반복을 하면 되는데 시간 초과 발생을 주의해야 한다.
• N개의 크레인에 대해 각각 M개 박스를 모두 탐색하면 불필요한 탐색이 있을 수 있다. 예를 들어 크레인과 박스 입력 정보가 다음과 같을 때를 보자.

• 무게 제한이 10인 크레인은 모든 박스를 들 수 있지만, 6은 6이하의 박스를, 5는 박스를 한 개도 들 수 없다.
• 이렇게 되면 굳이 M개의 박스를 모두 볼 필요 없다. 방문 배열로 건너뛸 순 있겠지만 어쨌든 반복은 필요하다.
• 이 점을 주의하면 시간 초과가 발생하지 않는다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N x M)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] cranes = new int[n];
        for (int i = 0; i < n; i++) {
            cranes[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());

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

        Arrays.sort(cranes);
        Arrays.sort(boxes);

        //가장 무거운 박스가 제일 무거운 무게를 들 수 있는 크레인의 무게 제한보다 무거우면 절대 모든 박스를 옮길 수 없다.
        if (boxes[m - 1] > cranes[n - 1]) {
            System.out.println(-1);
            return;
        }

        int[] craneIdx = new int[n];
        Arrays.fill(craneIdx, m - 1);

        boolean[] isMoved = new boolean[m];

        int count = 0;

        while (m > 0) {

            for (int i = n - 1; i >= 0; i--) {

                if (m == 0) break;

                for (int j = craneIdx[i]; j >= 0; j--) {
                    if (!isMoved[j]) {
                        //현재 크레인이 옮길 수 있는 박스면 옮긴다.
                        if (cranes[i] >= boxes[j]) {
                            isMoved[j] = true;
                            m--;
                            break;
                        } else {
                            craneIdx[i]--;
                            //현재 크레인이 들 수 있는 박스의 시작점을 조정한다.
                            //첫 번째 while 문이 끝나고 나면 자신이 들 수 있는 무게의 박스부터 탐색해 나간다.
                        }
                    }

                }
            }

            count++;
        }

        System.out.println(count);
    }
}