[Java] 백준 1092번 : 배

문제

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

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

입력

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

출력

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

예제 입력 1

3
6 8 9
5
2 5 2 4 7

예제 출력 1

2

예제 입력 2 

2
19 20
7
14 12 16 19 16 1 5

예제 출력 2 

4

예제 입력 3 

4
23 32 25 28
10
5 27 10 16 24 20 2 32 18 7

예제 출력 3 

3

예제 입력 4 

10
11 17 5 2 20 7 5 5 20 7
5
18 18 15 15 17

예제 출력 4 

2

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int N, M;
	private static List<Integer> limits, weights;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		
		N=Integer.parseInt(br.readLine());	// 각 크레인의 무게 제한 입력 및 내림차순 정렬
		limits=new ArrayList<>();
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) limits.add(Integer.parseInt(st.nextToken()));
		Collections.sort(limits, Collections.reverseOrder());
		
		M=Integer.parseInt(br.readLine());	// 각 박스의 무게 입력 및 내림차순 정렬
		weights=new ArrayList<>();
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<M;i++) weights.add(Integer.parseInt(st.nextToken()));
		Collections.sort(weights, Collections.reverseOrder());
		
		if(limits.get(0)<weights.get(0)) System.out.println(-1);	// 가장 무거운 박스를 옮길 수 있는 크레인이 존재하지 않으면 -1 출력
		else {	// 모든 박스를 배로 옮길 수 있는 경우
			int count=0;	// 시간 카운트
			while(weights.size()>0) {	// 옮겨야 할 박스의 개수가 0보다 크면 반복문 수행
				int idx=0;	// 박스 번호
				for(int i=0;i<N;) {	// 크레인을 탐색
					if(limits.get(i)>=weights.get(idx)) {	// 현재 박스를 옮길 수 있으면 리스트에서 박스 제거하고 다음 크레인 수행
						weights.remove(idx);
						i++;
					} else idx++;	// 현재 박스를 옮길 수 없으면 다음 박스 가능한지 확인
					if(idx==weights.size()) break;	// 모든 박스를 탐색한 경우 시간을 한번 증가시키고 다음 반목문 수행
				}
				count++;
			}
			
			System.out.println(count);
		}
	}

}

1. 가장 무거운 박스부터 옮길 수 있는지 확인해주기 위해 크레인과 박스를 각가 내림차순 정렬을 합니다.

2. 가장 무거운 박스를 옮길 수 있는 크레인이 없으면 -1을 출력합니다.

3. 모든 박스를 옮길 수 있는 경우 시간을 탐색합니다.

    3-1. 남아있는 박스의 개수가 0보다 크면 반복문을 수행합니다.

    3-2. 크레인의 개수만큼 반복문을 수행합니다.

        3-2-1. 현재 크레인 무게 제한이 현재 박스 무게보다 크거나 같으면 : 리스트에서 현재 박스를 제거하고 다음

                  크레인으로 옮겨줍니다.

        3-2-2. 현재 크레인 무게 제한이 현재 박스 무게보다 작으면 : 박스 인덱스를 1 증가합니다.

        3-2-3. 모든 박스를 탐색했으면 현재 반복문을 끝냅니다.

    3-3. 시간을 1만큼 증가시킵니다.