[Java] 백준 1092번 배

그리디 문제입니다.

크레인과 박스가 주어지고 배는 한번에 하나의 박스를 옮길 수 있습니다.
각 크레인마다 무게 제한이 있으며, 무게 제한 보다 큰 박스는 옮길 수 없습니다.
모든 박스를 크레인을 통해 옮기는데 걸리는 최솟값을 구해야합니다.

먼저 정렬을 해주었습니다.
그리고 각 크레인마다 들 수 있는 가장 높은것들부터 들도록 하였습니다.
가장 무게제한이 큰 크레인이 마지막 박스 까지 온 경우 종료하고 카운트한 값을 출력합니다.

불가능한 경우를 찾기위해
정렬한 후 크레인의 가장 큰 무게제한과 박스의 가장 큰 무게를 비교해서
박스가 더 큰 경우 불가능한 경우로 판단해주었습니다.

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

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = null;

    int n;
    int m;
    int[] crane;
    int[] cIndex;
    int[] box;
    int result;

    result = 0;
    n = Integer.parseInt(br.readLine());
    crane = new int[n];
    cIndex = new int[n];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; ++i) {
      crane[i] = Integer.parseInt(st.nextToken());
    }

    m = Integer.parseInt(br.readLine());
    box = new int[m];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < m; ++i) {
      box[i] = Integer.parseInt(st.nextToken());
    }

    Arrays.sort(crane);
    Arrays.sort(box);

    if (crane[n - 1] < box[m - 1]) {
      result = -1;
    } else {
      for (int i = 0; i < n; ++i) {
        cIndex[n - i - 1] = m - i - 1;
      }

      while (true) {
        for (int i = n - 1; i >= 0; --i) {
          while (cIndex[i] >= 0 && (box[cIndex[i]] <= 0 || crane[i] < box[cIndex[i]])) {
            --cIndex[i];
          }

          if (cIndex[i] < 0) {
            if (i == n - 1) {
              break;
            }
            continue;
          }

          if (crane[i] >= box[cIndex[i]]) {
            box[cIndex[i]] = 0;
          }
        }
        if (cIndex[n - 1] < 0) {
          break;
        }
        ++result;
      }
    }

    bw.write(result + "\n");
    bw.close();
  }
}