백준 1092

1092번: 배

---

문제

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

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

 

입력

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

 

출력

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

 

제한

• 시간 제한 : 2초
• 메모리 제한 : 128MB

---

문제 풀이 과정

시간 제한은 2초이고, N≤50, M≤10,000 이므로, 모든 박스를 크레인과 대조하면 M * N 으로 통과가 가능하다.

먼저 크레인과 박스를 입력받고 , 내림차순으로 정렬한다.

모든 박스를 옮겨야되기 때문에, 만약 크레인 MAX 값보다 박스 MAX 값이 더 크면 모든 박스를 옮기지 못하기 때문에 그대로 -1을 출력하면 된다.

그 후 박스 원소를 탐색하며, 크레인으로 옮길 수 있다면, 박스를 지우면서 탐색을 한다.

---

정답 코드

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

class Main1092 {

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

		int N = Integer.parseInt(br.readLine());
		List<Integer> cranes = new ArrayList<>();

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

		int M = Integer.parseInt(br.readLine());
		List<Integer> boxes = new ArrayList<>();

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

		cranes.sort(Collections.reverseOrder());
		boxes.sort(Collections.reverseOrder());

		if (cranes.get(0) < boxes.get(0)) {
			System.out.println(-1);
			return;
		}

		int ans = 0;
		while (!boxes.isEmpty()) {
			int boxIdx = 0;
			for (int i = 0; i < N; ) {
				if (boxIdx == boxes.size()) { //박스를 모두 탐색했다면 종료
					break;
				}

				if (cranes.get(i) >= boxes.get(boxIdx)) { //제거 가능하다면
					boxes.remove(boxIdx); //박스 삭제
					i++;
				} else {
					boxIdx++;
				}
			}
			ans++;
		}

		System.out.println(ans);
	}
}