[Baekjoon] 백준 1092: 배 - Java

문제

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

 

풀이

대표적인 그리디 문제이다.

1. 박스와 크레인의 무게를 내림차순으로 정렬해 준다.
2. 내림차순으로 정렬했을 때, 첫 번째 인덱스 값이 박스의 무게가 더 나간다면, -1을 출력한다.
3. 제일 중요한 부분인데, 크레인의 움직였던 위치를 배열을 만든다. (pos)
4. 크레인의 개수만큼 돌면서, 기존 크레인 위치에서 삭제 처리가 된 박스라면 크레인을 이동하고, 삭제 처리가 되지 않은 박스라면 삭제 처리를 하고 바로 빠져나와 크레인의 위치를 유지한다.
5. 삭제된 박스의 개수가 m과 같다면 모두 삭제되었으므로 while문을 빠져나온다.

 

그래서 최종 시간 복잡도는 O(50 * 10000)이다.

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Collections;
import java.util.ArrayList;

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> cranes = new ArrayList<>();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for (int i = 0; i < n; i++) {
			cranes.add(Integer.parseInt(st.nextToken()));
		}
		
		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(cranes, Collections.reverseOrder());
		Collections.sort(boxes, Collections.reverseOrder());
		
        //크레인의 무게보다 짐의 무게가 더 나간다면 => 불가능함
		if (cranes.get(0) < boxes.get(0)) {
			System.out.print(-1);
			return;
		}
		
        //크레인의 위치
		int[] pos = new int[n];
        
        //짐 제거 여부 배열
		boolean[] removed = new boolean[m];
		
        //정답
		int answer = 0;
        
        //제거된 짐의 개수
		int removeCount = 0;
		
		while(true) {
			if (removeCount == m) {
				break;
			}
			
			for (int i = 0; i < n; i++) {
				//하나의 포크레인에 대해서, 자기자신보다 같거나 작으면 바로 스톱
				for (int j = pos[i]; j < m; j++) {
					//삭제 처리가 되었다면, continue;
					if (removed[j]) {
						//크레인 위치 이동
						pos[i] += 1;
						
						continue;
					}
					
					if (cranes.get(i) >= boxes.get(j)) {
						//삭제 처리를 하고
						removed[j] = true;
						
						removeCount += 1;
						
						break;
					}
					
					//들 수 없으면 이동해버림
					pos[i] += 1;
				}
			}
			
			answer += 1; 
		}
		
		System.out.print(answer);

		br.close();
	}

}