[BaekJoon] 1092 배 (Java)

🔗 문제 링크

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

📝 문제풀이 방법

각각 무게 제한이 있는 N개의 크레인으로 M개의 컨테이너를 옮길 때 시간이 얼마나 걸리는지 구하는 문제이다.

문제를 해결하기 위해서는 컨테이너와 크레인을 각각 정렬한 후 각각의 크레인들이 현재 남아있는 컨테이너 중에서 자신이 들을 수 있는 가장 무거운 컨테이너들을 옮기도록 코드를 짜면 된다.

🚨 주의
처음에 문제를 풀며 매 시간당 크레인들이 index가 0인 컨테이너들부터 탐색을 하게 코드를 작성하였더니 컨테이너 이동이 완료가 됐거나 자신이 옮길 수 없는 무게임에도 불구하고 불필요한 탐색을 반복적으로 하게되어 시간초과가 나왔다.


그래서 start배열을 만들어 배번 crane이 탐색을 시작할 컨테이너를 변경해주도록 하였더니 시간초과가 나오지 않고 문제가 무사히 통과했습니다.

👨🏻‍💻 작성한 코드

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

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 크레인 무게 받기
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		Integer[] crane = new Integer[N];
		for (int i=0; i<N; i++) {
			crane[i] = Integer.parseInt(st.nextToken());
		}
		
		// 컨테이너 무게 받기
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		Integer[] container = new Integer[M];
		for (int i=0; i<M; i++) {
			 container[i] = Integer.parseInt(st.nextToken());
		}
		
		// 크레인과 컨테이너 무게 정렬
		Arrays.sort(crane, Collections.reverseOrder());
		Arrays.sort(container, Collections.reverseOrder());
		
		if (container[0] > crane[0]) System.out.println(-1);
		else {
			int result = 0;
			int[] start = new int[N];
			Arrays.fill(start, 0);
			while (M > 0) {
				for (int i=0; i<N; i++) { // 각각의 crane이 일함
					if (M < 1) break;
					for (int j=start[i]; j<container.length; j++) {
						if (container[j]==0 || container[j] > crane[i]) {
							start[i]++;
							continue;
						}
						container[j] = 0;
						M--;
						break;
					}	
				}
				result++;
			}
			System.out.println(result);
		}
	}
}