풀이

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @Author: kbs
 */
public class Main {

    static int N, M;
    static int[] crane, boxes;


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

        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        crane = new int[N];

        for (int i = 0; i < N; i++) {
            crane[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(crane);

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


        Arrays.sort(boxes);
        if (boxes[M - 1] > crane[N - 1]) {
            System.out.println(-1);
            return;
        }

        Deque<Integer> before = new ArrayDeque<>();
        Stack<Integer> after = new Stack<>();
        for (int i = M - 1; i >= 0; i--) {
            before.addFirst(boxes[i]);
        }

        int time = 0;
        while (true) {
            int craneNum = N - 1;
            while (!before.isEmpty() && craneNum >= 0) {
                int box = before.peekLast();
                if (crane[craneNum] >= box) {
                    before.pollLast();
                    craneNum--;
                } else {
                    after.add(before.pollLast());
                }
            }

            while (!after.isEmpty()) {
                before.addLast(after.pop());
            }
            time++;
            if (before.isEmpty()) break;
        }


        System.out.println(time);
    }
}

참고한 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @Author: kbs
 */
public class Main {

    static int N, M;
    static ArrayList<Integer> crane;
    static ArrayList<Integer> boxes;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        crane = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            crane.add(Integer.parseInt(st.nextToken()));
        }

        M = Integer.parseInt(br.readLine());
        boxes = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            boxes.add(Integer.parseInt(st.nextToken()));
        }

        crane.sort(Collections.reverseOrder());
        boxes.sort(Collections.reverseOrder());

        if (boxes.get(0) > crane.get(0)) {
            System.out.println(-1);
            return;
        }

        int ans = 0;

        while (!boxes.isEmpty()) {
            int idx = 0;
            for (int i = 0; i < N; ) {
                if (idx == boxes.size()) break;

                if (crane.get(i) >= boxes.get(idx)) {
                    boxes.remove(idx);
                    i++;
                } else idx++;
            }
            ans++;
        }

        System.out.println(ans);
    }
}

• 거의 10배가 넘게 시간 차이가 나서 왜인지 고민하는데 아직 잘 모르겠음.
  • List의 삭제 연산은 그 원소의 왼쪽 녀석들을 옆으로 밀어넣는 것으로 알고 있음.
    • 그래서 O(n)
  • 내 풀이는 정렬하고 Queue랑 Stack을 활용했다.
    • 그 턴에 못담으면 stack에 뒀다가 한바퀴 돌면 끝나고 다시 queue에 담는 방식.
    • 담을 수 있으면 삭제.
• ArrayList의 경우 연속되게 저장됨.
• ArrayDeque도 local하게.
• 둘다 그러면 조회속도 빨라야되는거 아닌가?
• resize문제도 크게 상관없음. -> 오히려 ArrayDeque는 사이즈 커지면 2배씩 늘려버림.
  스택오버플로우

결론

• 최악의 경우를 생각해보자
• box 10000개, 크레인 50개가 주어졌을 때, 모든 box가 다 가장 무거운 크레인에만 들어가야 한다면?
  • stack에 10000개 쌓아놨다가 돌려주고, 9999개 쌓아놨다가 돌려주고 ...
    계속 반복하게 됨.
• ㅇㅎ...