白駿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);
    	}
    }