1092 - 배

정답 아이디어

1. 크레인을 들 수 있는 무게에따라 역순 정렬, 박스도 역순 정렬 한다.

2. 역순 정렬 된 크레인을 앞에서부터 선택하며, 자신이 가질 수 있는 가장 큰 크기의 박스를 옮긴다.

3. 이 때 크레인이 박스를 옮기게 되면, 해당 크레인 idx를 1 늘려주고 다음 박스로 넘어간다.

Try 1. 메모리초과 (1%)

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

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] cr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i< cr.length;i++){
            cr[i] = Integer.parseInt(st.nextToken());
        }
        int M = Integer.parseInt(br.readLine());
        int[] box = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<box.length;i++){
            box[i] = Integer.parseInt(st.nextToken());
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            return Integer.compare(o2, o1);
        });
        for (int elem : box) pq.offer(elem);
        int time = 1;
        Queue<Integer> que = new ArrayDeque<>();
        int boxCnt = 0;
        while (true) {
            int tmp = boxCnt;
            for (int i=0; i<cr.length; i++) {
                while (!pq.isEmpty()){
                    int bx= pq.poll();
                    if (bx <= cr[i]){
                        boxCnt++;
                        break;
                    } else {
                        que.offer(bx);
                    }
                }
                while (!que.isEmpty()) pq.offer(que.poll());
            }
            if (boxCnt == box.length) {
                break;
            }
            if (tmp == boxCnt) {
                time = -1;
                break;
            }
            time++;
        }
        System.out.println(time);
    }
}

우선순위 큐 하나와, 일반 큐 하나를 사용해 풀이했다.

먼저 BIg-O 계산이 틀렸다. 처음으로 든 생각으로는, O(NM) 정도가 들거라 생각했다.

어차피 각 크레인이 박스를 꺼내 사용하고나면, 우선순위 큐에서 해당 박스가 사라지기 때문에

time이 늘어나는 만큼, 탐색해야 될 박스의 개수가 줄어듦으로 인해 평균회귀되어 O(NM)이라고 생각했지만,

naive하게 생각했을 경우 O(NM^2) 정도가 든다. 더군다나 평균회귀 된다고 해도, 각 크레인이 박스를 꺼내고나면 시도해본 다른 박스들을 다시 pq에 넣어주는데, 이 부분 때문에 메모리초과가 날 것이다.

 

Try 2. 시간초과 (1%)

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

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] cr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i< cr.length;i++){
            cr[i] = Integer.parseInt(st.nextToken());
        }
        int M = Integer.parseInt(br.readLine());
        Integer[] box = new Integer[M];
        boolean[] visited = new boolean[M];
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<box.length;i++){
            box[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(box, Collections.reverseOrder());
        int time = 1;
        int boxCnt = 0;
        while (true) {
            int tmp = boxCnt;
            for (int i=0; i<cr.length; i++) {
                for (int j = 0; j < box.length; j++) {
                    if (!visited[j] && box[j] <= cr[i]) {
                        visited[j] = true;
                        boxCnt++;
                        break;
                    }
                }
            }
            if (boxCnt == box.length) {
                break;
            }
            if (tmp == boxCnt) {
                time = -1;
                break;
            }
            time++;
        }
        System.out.println(time);
    }
}

 처음에 메모리 초과가 났을 때, Queue 2개를 사용한 것이 잘못됐다고 생각되었다. 그래서 Queue 두 개를 지우고, 해당 박스가 옮겨졌는지 체크하는 boolean 배열 하나를 추가한 형태로 구현했다.

여기서도 마찬가지로 naive하게 생각해보면 O(NM^2)의 시간복잡도를 가진다.

제일 큰 용량을 가진 크레인만 모든 박스를 옮길 수 있을 정도로 박스들의 크기가 크다고 생각해보면 이 때 O(NM^2)의 경우가 발생한다.

 

Try 3. 정답!

제출 번호	아이디	문제	문제 제목	결과	메모리	시간	언어	코드 길이	제출한 시간
66199228	kjy0349	1092	배	맞았습니다!!맞았습니다!!	15784KB	412ms	Java 8	1499	18분 전

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

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Integer[] cr = new Integer[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i< cr.length;i++){
            cr[i] = Integer.parseInt(st.nextToken());
        }
        int M = Integer.parseInt(br.readLine());
        Integer[] box = new Integer[M];
        boolean[] visited = new boolean[M];
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<box.length;i++){
            box[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(box, Collections.reverseOrder());
        Arrays.sort(cr, Collections.reverseOrder());
        int time = 1;
        int boxCnt = 0;
        while (true) {
            int tmp = boxCnt;
            int idx = 0;
            for (int j = 0; j < box.length; j++) {
                if (idx >= cr.length) break;
                if (!visited[j] && box[j] <= cr[idx]) {
                    visited[j] = true;
                    idx++;
                    boxCnt++;
                }
            }
            if (boxCnt == box.length) {
                break;
            }
            if (tmp == boxCnt) {
                time = -1;
                break;
            }
            time++;
        }
        System.out.println(time);
    }
}

O(M^2)를 보장하기 위해, 기존에 box만 정렬하는 방식에서 크레인의 크기도 같이 정렬해 가장 큰 크레인부터 해당 크레인이 옮길 수 있는 가장 큰 박스를 찾는 방식으로 구현했다.

가장 큰 크레인이 해당 박스를 옮기게 되면, 그 다음 크레인은 가장 큰 크레인이 옮긴 박스의 다음 인덱스에 존재하는 박스부터 탐색을 시작하면 된다. 이렇게 구현 할 경우, 각 크레인마다 다시 처음에 있던 박스부터 탐색하는 구간이 줄어들어 시간을 줄일 수 있게 된다.