白駿1092、倍加Greedy

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

1.アイデア

各クレーンの最大重量リスト、各箱の重量リストは大きな順序で

並べられている.

最大の箱で、最大のクレーンから始まります.

1)箱を対応するクレーンに移すことができれば、

リストから該当するブロック

を削除する.

次の箱、次のクレーン

をチェック
2)箱を該当するクレーンに移動できない

次の箱(現在の箱の重量より低い)が現在のクレーンに移動できることを確認します.
=>すべてのクレーンがチェックされている場合、経過時間+1

2.資料構造

2ArrayList<Integer>2個:各クレーンの最大重量リスト、各箱の重量リスト

3.時間複雑度

クレーン最大重量リスト:50 log 250~=250

箱重量リスト配列:10^4 log 2 10^4~=12 x 10^4

コード#コード#

import java.io.*;
import java.util.*;

public class Main {
	static int n;					// 크레인 개수
	static List<Integer> craneWeights = new ArrayList<>();		// 각 크레인의 최대 무게
	static int m;					// 박스 개수
	static List<Integer> boxWeights = new ArrayList<>();		// 각 박스의 무게
	static int minTime;				// 출력, 최소 시간

	static void solution() {
		// 박스를 모두 옮길 수 없는 경우
		if (boxWeights.get(0) > craneWeights.get(0)) {
			minTime = -1;
			return;
		}

		while (!boxWeights.isEmpty()) {
			int boxIdx = 0;

			for (int i = 0; i < craneWeights.size(); ) {	// 주의) for 문에 i++ 없음
				if (boxIdx == boxWeights.size())	// 마지막 박스까지 확인한 경우
					break;							// => 남은 첫 번째 박스, 첫 번째 크레인부터 다시 확인

				if (boxWeights.get(boxIdx) <= craneWeights.get(i)) {
					boxWeights.remove(boxIdx);		// 해당 박스 옮김(제거)
					i++;							// 다음 크레인
				}
				else				// [i] 크레인으로 박스 못 옮기는 경우
					boxIdx++;		// => [i] 크레인으로 다음 박스 옮길 수 있는지 확인
			}

			minTime++;
		}
	}

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

		n = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			craneWeights.add(Integer.parseInt(st.nextToken()));

		m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < m; i++)
			boxWeights.add(Integer.parseInt(st.nextToken()));

		// 2개 리스트를 각각 무게 큰 순으로 정렬
//		Collections.sort(craneWeights, (w1, w2) -> w2 - w1);
		Collections.sort(craneWeights, Collections.reverseOrder());
		Collections.sort(boxWeights, Collections.reverseOrder());

		solution();
		System.out.println(minTime);
	}
}