[백준 골드5] 1092번: 배 (그리디, 정렬) - Java

1092번: 배

https://www.acmicpc.net/problem/1092

 

문제
지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

출력
첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

예제 입력 1 
3
6 8 9
5
2 5 2 4 7
예제 출력 1 
2
예제 입력 2 
2
19 20
7
14 12 16 19 16 1 5
예제 출력 2 
4
예제 입력 3 
4
23 32 25 28
10
5 27 10 16 24 20 2 32 18 7
예제 출력 3 
3
예제 입력 4 
10
11 17 5 2 20 7 5 5 20 7
5
18 18 15 15 17
예제 출력 4 
2

---

알고리즘: 그리디 알고리즘, 정렬

풀이

시도

처음에는 crane은 배열로, box는 list로 담고 각각 Arrays.sort(), Collections.sort()로 정렬해서 풀었다. box를 list에 담은 이유는 중간의 box가 삭제될 수 있어 인덱스(순서)가 바뀌기 때문이었다.

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

public class Main
{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] crane = new int[n];
        String[] sb = br.readLine().split(" ");
        for(int i=0; i<n; i++) {
            crane[i] = Integer.parseInt(sb[i]);
        }
        Arrays.sort(crane); // 오름차순 정렬
        int m = Integer.parseInt(br.readLine());
        List<Integer> box = new ArrayList<>();
        sb = br.readLine().split(" ");
        for(int i=0; i<m; i++) {
            box.add(Integer.parseInt(sb[i]));
            if (box.get(i) > crane[n-1]) { // 모든 박스를 배로 옮길 수 없으면 -1 출력
                System.out.println(-1);
                return;
            }
        }
        Collections.sort(box); // 오름차순 정렬
        
        int time = 0;
        while (box.size() > 0) {
            for(int i=n-1; i>=0; i--) {
                for(int j=box.size()-1; j>=0; j--) {
                    if (crane[i] >= box.get(j)) {
                        box.remove(j);
                        break;
                    }
                }
            }
            time++;
        }
        System.out.println(time);
    }
}

 

추가 최적화를 위한 공부

내 기존 구현은 ArrayList.remove(index)를 사용하는데, 내부적 shift 연산이 O(M)이 든다. (-> 성능 병목, 전체 시간복잡도 O(NM^2))
이를 인덱스 기반 탐색과 boolean 마킹으로 변경하면 O(1)으로 가능해 효율성을 향상할 수 있다. (-> 전체 시간복잡도 O(NM))

 

사용하는 변수
- boolean used[]: 박스별로 처리 여부 마킹
- int pos[]: 크레인별로 현재 탐색해야 할 박스 인덱스 관리
=> 매번 O(1) 마킹/스킵 가능

 

또한 이번에는 인덱스를 끝부터 탐색하는 대신 Arrays.sort에 파라미터로 Collections.reverseOrder()를 전달해 내림차순 정렬해보았다.

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

public class Main
{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Integer[] crane = new Integer[n];
        String[] sb = br.readLine().split(" ");
        for(int i=0; i<n; i++) {
            crane[i] = Integer.parseInt(sb[i]);
        }
        Arrays.sort(crane, Collections.reverseOrder());

        int m = Integer.parseInt(br.readLine());
        Integer[] box = new Integer[m];
        sb = br.readLine().split(" ");
        for(int i=0; i<m; i++) {
            box[i] = Integer.parseInt(sb[i]);
            if (box[i] > crane[0]) {
                System.out.println(-1);
                return;
            }
        }
        Arrays.sort(box, Collections.reverseOrder());

        boolean[] used = new boolean[m];
        int[] pos = new int[n];
        int moved = 0;
        int time = 0;

        while (moved < m) {
            for (int i = 0; i < n; i++) {
                while (pos[i] < m) {
                    if (!used[pos[i]] && crane[i] >= box[pos[i]]) {
                        used[pos[i]] = true;
                        moved++;
                        pos[i]++;
                        break;
                    }
                    pos[i]++;
                }
            }
            time++;
        }
        System.out.println(time);
    }
}

 

실행 시간이 크게 차이나는 것을 확인할 수 있다.