문제

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

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

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

---

입력

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

---

출력

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

---

풀이

접근방법

시간제한 2초, 메모리 128MB이다.

1 ≤ N ≤ 50
1 ≤ M ≤ 10,000

전형적인 그리디 문제이다.

특별한 풀이 방법이 없다.

1. 무거운 순서부터 정렬을 한다. ( 크레인, 박스 모두)
	a. 가장 무거운 것을 옮길 수 있는 크레인이 가장 무거운 박스를 옮길 수 없다면 답은 -1.
2. 각 크레인은 들 수 있는것 중 가장 무거운 박스를 들어서 옮긴다.
	즉, 선택한 박스를 리스트에서 제거한다.
3. 모든 크레인이 1번씩 선택했다면, 시간을 증가 시킨다.

박스를 삭제하는 로직으로 인해서 LinkedList로 구현체를 변경하였더니 시간 초과가 발생한다.
아마 list.get() 을 수행하는 과정에서 시간복잡도에서 손해를 보는것이 삭제를 하는 비용보다 크기때문에 발생하는것으로 추정된다.

---

코드

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

public class Main {
	static List<Integer> cranes, boxes;

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

		cranes = new ArrayList<>();
		boxes = new ArrayList<>();
		int N = stoi(in.readLine());
		String[] splitedLine = in.readLine().split(" ");
		for (int i = 0; i < N; ++i)
			cranes.add(stoi(splitedLine[i]));

		int M = stoi(in.readLine());
		splitedLine = in.readLine().split(" ");
		for (int i = 0; i < M; ++i)
			boxes.add(stoi(splitedLine[i]));

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

		// 크레인이 들 수 있는 무게보다 무거운 박스가 있는 경우 옮길 수 없다.
		if (boxes.get(0) > cranes.get(0)) {
			System.out.println(-1);
		} else {
			int time = 0;
			while (!boxes.isEmpty()) {
				time++;
				for (int i = 0; i < N; ++i) {
					for (int j = 0; j < boxes.size(); ++j) {
						if (cranes.get(i) >= boxes.get(j)) {
							boxes.remove(j);
							break;
						}
					}
				}
			}
			System.out.println(time);
		}
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}