[백준] 1092: 배 JAVA

접근

접근 자체는 어렵지 않은 문제였던 것 같다. 크레인과 박스의 무게를 내림차순으로 정렬하여, 무거운 것부터 크레인에 하나씩 할당해주면 된다. 그럼 이제 그걸 어떻게 구현하느냐의 문제이다. 해당 짐을 실었는지 여부를 확인하는 방법은 다양하게 있겠지만, 결국 원본 리스트에서 remove를 하는 것이 제일 간편한 방식이다. 그래서 일반 일차원 배열보다는 ArrayList에 저장하여 remove 함수를 쓰기로 했다. 다만 remove 사용 시 주의할 점은, 전체 리스트의 길이가 동적으로 변하기 때문에 반복문을 돌 때 인덱스를 넘어가지 않도록 조심해야 한다.

 

코드

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        // 입력값 저장
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> crains = new ArrayList();
        
        for(int i = 0;i < n;i++)
            crains.add(Integer.parseInt(st.nextToken()));

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> boxes = new ArrayList();
        
        for(int i = 0;i < m;i++)
            boxes.add(Integer.parseInt(st.nextToken()));

        // 내림차순 정렬
        Collections.sort(crains, Collections.reverseOrder());
        Collections.sort(boxes, Collections.reverseOrder());

        int answer = solve(crains, boxes);
        System.out.println(answer);
    }

    static int solve(ArrayList<Integer> crains, ArrayList<Integer> boxes){
        int result = 0;

        // 불가능한 경우
        if(boxes.get(0) > crains.get(0)){
            result = -1;
            return result;
        }

        // 그리디 계산
        while(!boxes.isEmpty()){
            int boxIdx = 0;
            int crainIdx = 0;
            int crainSize = crains.size();

            while(crainIdx < crainSize){
                if(boxIdx >= boxes.size())
                    break;

                if(crains.get(crainIdx) >= boxes.get(boxIdx)){
                    boxes.remove(boxIdx);
                    crainIdx++;
                }
                else boxIdx++;
            }
            result++;            
        }
        
        return result;
    }
}