[백준/BOJ] 1092번 배 자바 풀이

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

1092번: 배

 

 

박스 list와 크레인 배열을 모두 내림차순으로 정렬한다.

가장 무거운 박스부터 크레인으로 옮길 수 있는지 확인해야 하므로

box.get(0)으로 가장 앞에 있는 박스를 가져온다.

 

- 만약 크레인으로 옮길 수 있는 박스라면 박스 list에서 삭제하고, 크레인의 인덱스를 1 증가시킨다.

- 크레인으로 옮길 수 없는 박스라면 박스 list의 가장 맨 뒤로 이동시킨다.

- 만약 현재의 크레인으로 옮길 수 있는 박스가 하나도 존재하지 않는다면,

동시에 움직일 수 있는 크레인은 모두 구했으므로 다시 크레인의 인덱스를 0으로 설정하여 동시에 움직일 수 있는 박스를 제거해나간다. 이때 answer를 1 증가시킨다.

- 크레인의 인덱스를 증가시키다가 크레인 인덱스 범위를 벗어나면, 동시에 움직일 수 있는 크레인을 모두 구한 것이므로 동일하게 크레인의 인덱스를 0으로 설정하고, answer를 1 증가시킨다.

 

- 크레인으로 옮길 수 없는 박스를 list 맨 뒤로 이동시킬 때 바로바로 이동시키는 경우,

현재 크레인으로 옮길 수 있는 박스가 존재하는지 판단할 때 계속 list를 정렬시켜줘야 한다.

즉, 이동시켜야할 박스를 temp라는 list에 저장한 후, 크레인의 인덱스를 0으로 다시 설정하는 경우(동시에 움직일 수 있는 박스를 모두 구한 경우) 한꺼번에 박스 list에 이동시킨다.

- 박스 list에 옮겨야할 temp list는 비어있지 않은데 박스 list는 비어있는 경우 now_box를 구할 때 오류가 날 수 있다. 그 경우 now_box를 -1으로 두어 처리했다.

 

 

 

다른 분들 코드를 보니 전체적인 풀이 방식은 비슷한데,

내가 좀 더 꼬아서 생각한듯 하다. 코드가 지저분하다..

 

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

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

		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++)
			crane[i] = Integer.parseInt(st.nextToken());

		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()));

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

		if(box.get(0) > crane[0]) { // 가장 무거운 박스가 가장 큰 크레인의 무게 제한보다 크다면 배로 옮길 수 없음
			System.out.println(-1);
			return;
		}

		ArrayList<Integer> temp = new ArrayList<>();
		int answer = 1;
		int idx = 0; // crane 배열 인덱스

		while(!box.isEmpty() || !temp.isEmpty()) {
			if(idx >= N) {
				answer++;
				idx %= N;
				box.addAll(temp);
				temp.clear();
				box.sort(Collections.reverseOrder());
			}

			int now_box = box.isEmpty() ? -1 : box.get(0);
			if(now_box != -1 && now_box <= crane[idx]) { 
				idx++;
				box.remove(0);
			}
			else {
				if(now_box == -1 || crane[idx] < box.get(box.size() - 1)) {
					answer++;
					idx = 0;
					box.addAll(temp);
					temp.clear();
					box.sort(Collections.reverseOrder());
				}
				else {
					box.remove(0);
					temp.add(now_box); // 현재 크레인으로 움직일 수 없는 경우 리스트 뒤에 넣기
				}
			}		
		}

		System.out.println(answer);
	}

}