[백준] 1092번. 배(JAVA)

문제

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

---

풀이(40분)

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

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

        int n = Integer.parseInt(br.readLine()); // 크레인 개수
        Integer[] crane = new Integer[n]; // 크레인 배열
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            crane[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(crane, Collections.reverseOrder()); // 크레인 내림차순 정렬

        int m = Integer.parseInt(br.readLine()); // 박스 개수
        ArrayList<Integer> boxes = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            boxes.add(Integer.parseInt(st.nextToken()));
        }
        Collections.sort(boxes, Collections.reverseOrder()); // 박스 내림차순 정렬

        // 박스를 전부 옮길 수 없는 경우 (가장 강한 크레인보다 무거운 박스가 존재)
        if (boxes.get(0) > crane[0]) {
            System.out.println(-1);
            return;
        }

        int time = 0; // 걸리는 시간
        while (!boxes.isEmpty()) {
            int boxIndex = 0;
            for (int i = 0; i < n; i++) { // 각 크레인이 박스를 최대한 옮기도록 한다.
                if (boxIndex >= boxes.size()) break; // 박스가 다 옮겨졌다면 종료
                if (crane[i] >= boxes.get(boxIndex)) { // 크레인이 박스를 옮길 수 있다면
                    boxes.remove(boxIndex); // 박스 제거
                } else {
                    boxIndex++; // 더 작은 박스를 찾는다.
                    i--; // 현재 크레인이 다시 시도할 수 있도록 i 유지
                }
            }
            time++; // 1분 경과
        }

        System.out.println(time);
    }
}

import java.io.*;
import java.math.BigDecimal;
import java.util.*;

public class Main {

    // 정렬 시켜두고 뒤에서부터 쪼여가면서 찾자

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

        int n = Integer.parseInt(br.readLine()); // 크레인 개수
        int[] crane = new int[n]; // 크레인 배열
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            crane[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(crane); // 정렬

        int m = Integer.parseInt(br.readLine()); // 박스 개수
        int[] box = new int[m]; // 박스 배열
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++){
            box[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(box); // 정렬

        int min = (int) Math.ceil(m / (double)n); // 최초의 평균 개수
        
        if(crane[n-1] < box[m-1]){
            System.out.println(-1);
            return;
        }

        loop1:
        while(true){
            int boxIdx = m - 1;
            int craneIdx = n - 1;
            while(craneIdx >= 0 && boxIdx >= 0){
                if(box[boxIdx] <= crane[craneIdx]){ // 박스 최대 무게가 크레인의 무게보다 작거나 같다면
                    boxIdx -= min; // 박스 인덱스 감소
                    craneIdx--; // 크레인 인덱스 감소
                    continue;
                }
                min++; // 찾기에 실패한 경우 크레인 하나 당 개수를 늘림
                if(min > m){ // 크레인 하나 당 개수가 m을 초과한 경우 
                    System.out.println(-1); // -1 출력
                    return;
                }
                continue loop1;
            }
            System.out.println(min);
            break;
        }
    }
}
/*
4
1 1 1 1
9
1 1 1 1 1 1 1 1 1
 */

---

문제 풀이 전략

 

첫 번째 풀이는 지피티의 풀이를 참고한 것이고, 두 번째 풀이는 내가 풀이한 것이다.

 

내 풀이부터 정리하자면 무게를 가장 많이 들 수 있는 크레인부터 최소의 개수를 책임지는 것을 목표로 한다.

1. 평균적으로 몇개를 들어야 하는지 구한 후 올림한다. -> 좋은 크레인이 최대한 들게 하기 위함

2. 크레인이 들 수 있는 무게가 현재 박스 무게보다 크거나 같다면, 박스는 크레인이 책임진 수만큼, 크레인은 1만큼 인덱스를 감소한다.

3. 2번을 반복한다.

4. 최종적으로 만족시키지 못했다면, 좋은 크레인들이 하나씩 더 들게 책임을 키운다.

 

이를 반복하는 것이다. 즉, 내 코드는 반복을 최소화하여 문제를 해결하는 것이었다.

 

지피티의 코드를 가져온 이유는 n = 50, m = 10000이라는 제한 안에서 모두 반복하여 해결하는 방식이기 때문이다.

뭐.. 그럴 수도 있는데 왜 가져왔을까?

 

while (!boxes.isEmpty()) {
    int boxIndex = 0;
    for (int i = 0; i < n; i++) { // 각 크레인이 박스를 최대한 옮기도록 한다.
        if (boxIndex >= boxes.size()) break; // 박스가 다 옮겨졌다면 종료
        if (crane[i] >= boxes.get(boxIndex)) { // 크레인이 박스를 옮길 수 있다면
            boxes.remove(boxIndex); // 박스 제거
        } else {
            boxIndex++; // 더 작은 박스를 찾는다.
            i--; // 현재 크레인이 다시 시도할 수 있도록 i 유지
        }
    }
    time++; // 1분 경과
}

 

이 부분의 코드같이 구현하는걸 처음 봤기 때문이다.

 

박스는 리스트로 선언되어있다.

박스 인덱스를 0으로 해서 시작한다.

 

예를 들어, n = 1 2 3, m = 1 2 3 4 5라고 치자.

그럼 정렬이 역순으로 되었기 때문에 3 2 1과 5 4 3 2 1이 된다.

i = 0일 때, crane[0] >= boxes.get(0)에 의해 인덱스 0이 제거되고, 모두 한 칸씩 당겨진다.

i = 1일 때, crane[1]은 3이고 boxes.get(0)은 4이기 때문에 els 조건절로 넘어간다. 

-> boxIndex = 1, i = 0이 된다.

i = 1 일 때가 다시 반복된다.

-> 내가 중요하게 생각한 부분이다. 고의적으로 반복 조건을 감소시킴으로써 제자리에 머물게 한 것이다.

 

이 구현을 눈에 익혀두고, 필요한 경우 사용할 수 있어야 할 것 같다.