JAVA 백준 1092 배 (그리디)

 

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

 

---

문제

1. 첫째 줄에 크레인의 수 N ( 1 <= N <= 50 )이 입력된다.
2. 둘째 줄에 각 크레인의 무게 제한 (1 <= 무게 제한 <= 1000000 )이 공백으로 구분되어 입력된다.
3. 셋째 줄에 박수의 수 M ( 1 <= M <= 10000 )이 입력된다.
4. 넷째 줄에는 각 박스의 무게 (1 <= 박스 무게 <= 1000000 )가 공백으로 구분되어 입력된다.
5. 각 크레인은 1분에 박스를 하나씩 실을 수 있고 모든 크레인은 동시에 움직인다.
6. 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다.
7. 모든 박스를 배로 옮기는 데에 드는 시간의 최솟값을 출력하라.

---

 

 

 

 

저번에 풀었던 문제 이어서

https://gamja00.tistory.com/84

 

 

정답 코드 (수정 필요)

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

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[] crane = new Integer[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            crane[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(crane, Comparator.reverseOrder());

        int M = Integer.parseInt(br.readLine());

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


        if (crane[0] < box.get(0)) {
            System.out.println(-1);
            return;
        }


        int count = 0;

        while (!box.isEmpty()) {
            for (int i = 0; i < N; i++) {
                int j = 0;

                while (j < box.size()) {
                    if (crane[i] >= box.get(j)) {
                        box.remove(j);
                        break;
                    } else {
                        j++;
                    }
                }
            }

            count++;
        }

        System.out.println(count);
    }
}

 

 

방법은 맞는 것 같은데 계산하는 부분에서 시간이 좀 오래 걸리는 것 같아 해당 반복문들의 수정이 필요한 것 같다.

 

크레인과 박스의 각 무게들을 배열에 넣어 내림차순 정렬한 후 앞에서부터 비교하였다.

가장 무거운 무게를 옮길 수 있는 크레인이 가장 무거운 박스를 옮기는 것이 효율적이기 때문이다.

크레인을 기준으로 박스의 무게를 비교하여 조건식을 세워주었는데 각 크레인마다 박스를 0번부터 비교하기 때문에 시간이 오래 걸리는 듯하다.

 

 

 

 

 

정답 코드

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

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[] crane = new Integer[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            crane[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(crane, Comparator.reverseOrder());

        int M = Integer.parseInt(br.readLine());

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


        if (crane[0] < box.get(0)) {
            System.out.println(-1);
            return;
        }


        int count = 0;

        while (!box.isEmpty()) {
            int i = 0;
            int j = 0;
            while (i < N) {
                if (crane[i] >= box.get(j)) {
                    box.remove(j);
                    i++;
                } else {
                    j++;
                }
                if (j == box.size()) {
                    break;
                }
            }
            count++;
        }

        System.out.println(count);
    }
}

 

많이 달라진 건 없는 것 같은데 시간은 열 배가 차이난다.

 

반복문 중 하나가 빠졌고 해당 반복문은 변수로 바꾸어 따로 계산해준다.

두 개의 배열은 똑같이 내림차순으로 정렬해주었다.

이 때 크레인이 지정된 박스를 옮길 수 있다면 박스 목록에서 해당 박스를 제거하고 사용된 크레인을 넘기고 다른 크레인을 사용할 수 있도록 코드를 지정해준다.

크레인이 지정된 박스를 옮길 수 없다면 더 가벼운 박스를 옮길 수 있도록 박스를 가리키는 변수를 1 증가시켜 다음 박스와 비교할 수 있도록 한다.

 

이렇게 값을 같이 증가시키도록 설정하여 모든 값을 비교하지 않아도 정답을 얻게 코드를 작성하였다.