[백준] 1092번 : 배 Gold5(골드5) - JAVA[자바]

[Gold V] 배 - 1092

문제 링크

성능 요약

메모리: 15180 KB, 시간: 284 ms

분류

그리디 알고리즘, 정렬

제출 일자

2024년 6월 16일 20:34:37

문제 설명

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

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

입력

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

출력

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

접근 방법

1. 각 크레인이 옮길 수 있는 무게를 역순으로 정렬 시켜준다.
2. 리스트를 순회하며 각 크레인이 옮길 수 있는 최대 무게들을 옮겨준다.
3. 시간 복잡도는 O(N * M) + 정렬 시간으로 충분함

 

풀이 코드

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

/**
 * 문제: BOJ_1092_G5_배
 * 메모리: 15180KB
 * 시간: 284ms
 * 접근 방법
 * 1. 각 크레인이 옮길 수 있는 무게를 역순으로 정렬 시켜준다.
 * 2. 리스트를 순회하며 각 크레인이 옮길 수 있는 최대 무게들을 옮겨준다.
 * 3. 시간 복잡도는 O(N * M) + 정렬 시간으로 충분함
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> crane= new ArrayList<>();

        // Input
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            crane.add(Integer.parseInt(st.nextToken()));
        }// Input End

        // Input
        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()));
        }// Input End

        box.sort(Collections.reverseOrder());
        crane.sort(Collections.reverseOrder());

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

        int t = 0;
        while (!box.isEmpty()) {
            int craneIdx = 0, boxIdx = 0;
            int boxSize = box.size();
            while (craneIdx < N && boxIdx < boxSize) {
                if(crane.get(craneIdx) >= box.get(boxIdx)) {
                    box.remove(boxIdx);
                    boxSize--;
                    craneIdx++;
                }else{
                    boxIdx++;
                }
            }
            t++;
        }
        System.out.println(t);
    }
}