[백준] 배 : 1092 : Java - 그리디 (G5)

1.  💎 문제

 

---

 

 

2. 🤔 어떻게 풀까

• N개의 크레인 -> 동시에 이용 가능
• 각 크레인에는 실을 수 없는 무게 제한이 있음(포함)

이 두가지 조건을 중심으로 생각했다. 최소의 시간이 걸리기 위해서는 크레인들에게 균형있게 화물을 분배해줘야 한다. 이때 무게가 작은 박스는 어떠한 크레인이든 사용할 수 있지만, 무게가 커질 수록 사용할 수 있는 크레인은 적다. 그러므로 무게가 무거운 박스를 어떻게 분배하면 좋을지 생각했다. 

 

해답은 무거운 박스부터 적절한 크레인을 선택하여 싣게하는 것이다. 적절한 크레인을 어떻게 고르냐 생각했을 때, 그 순간 무게 제한이 박스의 무게를 포함하면서, 이동시켜야할 박스의 수가 제일 적은 것을 선택하기로 했다. 결국 중요한 것을 균형있는 분배이다. 그러므로 제일 작업량이 작은 크레인을 선택하는 것이다.

 

 

 

3. 💡 로직

1 . 상자와 크레인 정보 입력받기

리스트로 상자와 크레인의 정보를 입력받는다. 크레인은 제한 무게와 작업량을 저장해야 되기 때문에 별도의 클래스로 선언했다.

 public static void input() throws Exception {
        crane = new ArrayList<>();
        boxs = new ArrayList<>();

        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 상자 제한 무게 입력
        for(int i=0; i<N; i++){
            int limit = Integer.parseInt(st.nextToken());
            crane.add(new Crane(limit));
        }

        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        // 박스 무게 입력
        for(int i=0; i<M; i++){
            boxs.add(Integer.parseInt(st.nextToken()));
        }
    }
    
    class Crane {
    int limit;
    int count;

    public Crane(int limit){
        this.limit = limit;
        this.count = 0;
    }

    public void addBox(){
        count++;
    }
}

 

 

2. 솔루션

2.1 내림차순으로 정렬

가장 무거운 상자부터 확인해야 되기 때문에 편의를 위해 내림차순 정렬을 했다. 크레인도 마찬가지로 내림차순 정렬을 한다.

		// 박스 내림차순 정렬
        boxs.sort(Comparator.reverseOrder());
        // 크레인 내림차순 정렬
        crane.sort(new Comparator<Crane>() {
            @Override
            public int compare(Crane o1, Crane o2) {
                return o2.limit- o1.limit;
            }
        });

 

 

2.2 무거운 상자부터 적절한 크레인 찾아가기

가장 무거운 상자부터 탐색을 진행한다. 찾아야 되는 것은 나(박스)의 무게를 실을 수 있는 크레인 중 현재 작업량이 가장 적은 크레인이다. 

박스의 무게를 실을 수 없는 크레인이 나올 때까지 탐색을 진행하며, `count`변수를 이용해 작업량이 적은 크레인을 찾는다.

 

작업량이 적은 크레인으로 선택된 크레인의 `addBox()`를 호출하여 count를 1증가 시킨다. 이때 `craneIdx`가 0이면 어떠한 크레인으로 들 수 없으므로 문제의 조건에 맞게 -1를 출력한다.

	// 크레인이 이동 시켜야 할 상자 갯수
        int result [] = new int[N];
        Arrays.fill(result, Integer.MAX_VALUE);

        int boxIdx, craneIdx;
        for(boxIdx=0; boxIdx< M; boxIdx++){
            int crainNumber = 0;
            for(craneIdx = 0; craneIdx<N; craneIdx++){
                Crane curCrain = crane.get(craneIdx);
                if(curCrain.limit < boxs.get(boxIdx))
                    break;
                // 작은 count를 가지는 crain찾기
                if(curCrain.count < crane.get(crainNumber).count){
                    crainNumber = craneIdx;
                }
            }
            // 어떠한 크레인으로도 들 수 없을 때
            if(craneIdx==0){
                ans = -1;
                return;
            }
            // 해당 크레인의 count 1증가
            crane.get(crainNumber).addBox();
        }

 

2.3 가장 큰 count 구하기

`cranes`들을 비교하며, 가장 큰 count를 찾는다. 바로 그것이 총 작업시간이다.

	// 가장 큰 count 구하기
        int max = Integer.MIN_VALUE;
        for(Crane c : crane){
            if(c.count > max){
                max = c.count;
            }
        }
        ans = max;

 

3. 출력

public static void output() throws Exception{
        bw.write(ans+"\n");
        bw.flush();

        bw.close();
        br.close();
    }

 

---

 

 

4.  🖥️ 전체 코드

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

public class Main{
    static BufferedReader br;
    static BufferedWriter bw;
    static List<Crane> crane;
    static List<Integer> boxs;
    static int N;
    static int M;
    static int ans;

    public Main(){
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
    }

    public static void run() throws Exception {
        input();
        solution();
        output();
    }

    public static void input() throws Exception {
        crane = new ArrayList<>();
        boxs = new ArrayList<>();

        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 상자 제한 무게 입력
        for(int i=0; i<N; i++){
            int limit = Integer.parseInt(st.nextToken());
            crane.add(new Crane(limit));
        }

        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        // 박스 무게 입력
        for(int i=0; i<M; i++){
            boxs.add(Integer.parseInt(st.nextToken()));
        }
    }

    public static void solution(){
        // 박스 내림차순 정렬
        boxs.sort(Comparator.reverseOrder());
        // 크레인 내림차순 정렬
        crane.sort(new Comparator<Crane>() {
            @Override
            public int compare(Crane o1, Crane o2) {
                return o2.limit- o1.limit;
            }
        });

        // 크레인이 이동 시켜야 할 상자 갯수
        int result [] = new int[N];
        Arrays.fill(result, Integer.MAX_VALUE);

        int boxIdx, craneIdx;
        for(boxIdx=0; boxIdx< M; boxIdx++){
            int crainNumber = 0;
            for(craneIdx = 0; craneIdx<N; craneIdx++){
                Crane curCrain = crane.get(craneIdx);
                if(curCrain.limit < boxs.get(boxIdx))
                    break;
                // 작은 count를 가지는 crain찾기
                if(curCrain.count <= crane.get(crainNumber).count){
                    crainNumber = craneIdx;
                }
            }
            // 어떠한 크레인으로도 들 수 없을 때
            if(craneIdx==0){
                ans = -1;
                return;
            }
            // 해당 크레인의 count 1증가
            crane.get(crainNumber).addBox();
        }

        // 가장 큰 count 구하기
        int max = Integer.MIN_VALUE;
        for(Crane c : crane){
            if(c.count > max){
                max = c.count;
            }
        }
        ans = max;
    }
    public static void output() throws Exception{
        bw.write(ans+"\n");
        bw.flush();

        bw.close();
        br.close();
    }

    public static void main(String [] args) throws Exception{
        new Main().run();
    }
}

class Crane {
    int limit;
    int count;

    public Crane(int limit){
        this.limit = limit;
        this.count = 0;
    }

    public void addBox(){
        count++;
    }
}