오늘 풀어볼 문제는 ⭐배 라는 문제이다.

1. 문제요약

• 크레인 N개(최대 50), 박스 M개 (최대 10만개)가 주어짐
• 크레인은 들 수 있는 무게제한이 존재. 1분에 박스 1개씩, 동시 작업이 가능
• 크레인으로 박스를 옮길 수 있는 최소 시간 구하기(불가능 시 -1)

1.1 입력

• 1<=크레인 감당 가능 무게<=1,000,000
• 1<=박스 무게<=1,000,000

---

2. 접근법

크레인의 할당 조건 = 남은 박스 중 크레인이 들 수 있는 최대 값

이 문제는 단순 브루트포스로 풀게 되면

크레인 최대 개수 x 크레인 1개당 박스 리스트 돌기 x 박스최대개수/크레인최대개수 만큼 반복

• 한 턴에 최대 N × M = 50 × 10,000 = 500,000
• 그걸 최대 200번 반복

→ 총 연산 = 500,000 × 200 = 100,000,000 (1억)

즉 시간 안에 연산은 가능하다. 실제로 브루트포스만을 이용한 코드는 다음과 같고, 문제도 시간 내로 통과했다.

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

public class Main {
    static int N, M;
    static int[] crane;
    static int[] box;
    static boolean[] visited;

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

        // 입력 받기
        N = Integer.parseInt(br.readLine());
        crane = new int[N];

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

        M = Integer.parseInt(br.readLine());
        box = new int[M];
        visited = new boolean[M];

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

        // 크레인, 박스 내림차순 정렬
        Arrays.sort(crane);
        Arrays.sort(box);
        reverse(crane);
        reverse(box);

        // 가장 무거운 박스를 가장 센 크레인도 못 들면 -1
        if (box[0] > crane[0]) {
            System.out.println(-1);
            return;
        }

        int time = 0;
        int moved = 0;

        while (moved < M) {
            int boxIdx = 0;
            for (int i = 0; i < N; i++) { // 각 크레인
                while (boxIdx < M) {
                    if (!visited[boxIdx] && crane[i] >= box[boxIdx]) {
                        visited[boxIdx] = true;
                        moved++;
                        boxIdx++;
                        break;
                    }
                    boxIdx++;
                }
            }
            time++;
        }

        System.out.println(time);
    }

    static void reverse(int[] arr) {
        int l = 0, r = arr.length - 1;
        while (l < r) {
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
            l++;
            r--;
        }
    }
}

한 가지 까다로운건, 바로 배열을 무조건 내림차순으로 정렬 해야 한단 것이다.

배열을 오름차순 정렬하지 않으면 다음과 같은 예시에서 막히게 된다.

입력
4
1 2 3 4
8
1 1 2 2 3 3 4 4

올바른 출력
2

오류 출력
4

[오름차순 정렬 시]

• (1,1,2,2,) (3 3), (4), (4) 로밖에 들지 못하므로 4의 시간이 걸린다.
  즉, (1,2,3,4) (1,2,3,4) 라는 최적의 값을 찾지 못합니다.

[내림차순 정렬 시]
crain이 내림차순 정렬되어 (4, 3, 2, 1) 이 된다. 내림차순 정렬을 하는 이유는, 남은 박스중 무거운 박스부터 담아야 무거운 크레인이 가벼운 박스를 담는 일이 없다.

box가 내림차순 정렬되어 (4, 4, 3, 3, 2, 2, 1, 1) 이 된다.

첫번쨰 크레인인 4가 4 를 돌고, 3이 4를 돌고, 2가 2를 돌고 1이 1을 돈다.

또 4가 4 를 돌고, 3이 4를 돌고, 2가 2를 돌고 1이 1을 돕니다. 이렇게 되면 2번만에 처리가 가능하다.

2.1 알고리즘

완전탐색으로도 풀 수는 있지만, 더 나은 최적화를 위해선 하나만 더 추가해주면 된다.
바로 각 크레인이 이전 for문에서 box 배열의 어느 위치까지 탐색했었는지 위치만 기억해주면 된다.

즉 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static int N,M;
	public static Integer[] crain, box;
	public static int answer =0 ;
	public static boolean[] visited;
	public static int[] crain_positions;
    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());
    	crain = new Integer[N];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		crain[i] = Integer.parseInt(st.nextToken());
    	}
 
    	st = new StringTokenizer(br.readLine());
    	M = Integer.parseInt(st.nextToken());
    	box = new Integer[M];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<M;i++) {
    		box[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	//내림차순으로 정렬하여야, 큰것들부터 처리합니다. (큰 크레인이 작은것들을 처리하는 일이 없어야만 합니다.)
    	Arrays.sort(crain, Collections.reverseOrder());
    	Arrays.sort(box, Collections.reverseOrder());
    	
    	
    	if(crain[0] < box[0]) {
    		System.out.println("-1"); 
    		return;
    	}
 
    	crain_positions = new int[N];
    	visited = new boolean[M];
    	//박스를 모두 옮기기전까지 작동
    	while(M > 0) {
    		
    		//각 크레인이 순회
    		for(int i=0;i<N;i++) {
    			if(M == 0) break;
    			
    			for(int j=crain_positions[i];j<box.length;j++) {
    				if(visited[j] == true) continue; 
    				if(crain[i] < box[j]) {
    					crain_positions[i]++;
    					continue;
    				}
    				else if(crain[i] >= box[j]) {
    					visited[j] = true;
    					M--;
    					break;
    				}
    			}
    		}
    		answer++;
    	}
    	System.out.println(answer);
    	
    }
}

3. 팁

오늘의 꿀팁

"들 수 있는 것 중 최대 무게(값)를 할당해야 하는 문제라면, 반드시 내림차순 정렬이 필요함!."