BOJ 1092 : 배

문제링크

풀이요약

정렬

풀이상세

1. 크레인과 박스 모두 큰 순서부터 옮긴다. 단, 임의의 크레인보다 임의의 크레인보다 무거운 경우에는 다음 박스를 찾아 나른다.

2. 단순 반복의 경우 $O(N*M^2)$ 의 시간 복잡도가 나타나게 되는데, 자바에서는 시간초과가 나타난다. 해당 문제를 해결하기 위해 나의 경우 크레인 순서를 idx에 저장하는 방식을 통해, 재탐색과정을 생략했다.

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

public class Main {
    static int N, M, ans;
    static List<Integer> a, b;

    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer stk = new StringTokenizer(br.readLine());
        a = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            a.add(Integer.parseInt(stk.nextToken()));
        }
        Collections.sort(a, (a, b) -> b - a);
        M = Integer.parseInt(br.readLine());
        stk = new StringTokenizer(br.readLine());
        b = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            b.add(Integer.parseInt(stk.nextToken()));
        }
        Collections.sort(b, (a, b) -> b - a);
    }

    private static void solve() {
        if (b.get(0) > a.get(0)) {
            ans = -1;
            return;
        }

        while (!b.isEmpty()) {
            int idx = 0;
            for (int i = 0; i < a.size(); i++) {
                if (idx == b.size()) break;
                else if (a.get(i) >= b.get(idx)) {
                    b.remove(idx);
                } else {
                    idx++;
                    i--;
                }
            }
            ans++;
        }
    }

    private static void output() {
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        solve();
        output();
    }
}