[알고리즘-PS] 백준 1092번 배 자바 문제풀이

문제

해당 포스팅은 백준의 1092번 배 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

1092번: 배

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이 문제는 그리디 알고리즘을 이용해서 풀 수 있는 문제이다.

 

해결법

 

이 문제를 보고 캐치해야할 가장 중요한 단서는 바로 어떤 기준으로 정렬을 할 것인지이다.

 

이번 문제같은 경우는 박스의 무게와 크레인의 내림차순 정렬을 해야지 해결할 수 있다.

 

정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        ArrayList<Integer> cranes = new ArrayList<>();
        ArrayList<Integer> boxes = new ArrayList<>();

        String[] craneString = br.readLine().split(" ");

        for(String crane : craneString) {
            cranes.add(Integer.parseInt(crane));
        }

        int m = Integer.parseInt(br.readLine());

        String[] boxString = br.readLine().split(" ");

        for(String box : boxString) {
            boxes.add(Integer.parseInt(box));
        }

        Collections.sort(cranes, Collections.reverseOrder());
        Collections.sort(boxes, Collections.reverseOrder());

        if(cranes.get(0) < boxes.get(0)) {
            bw.write(String.valueOf(-1));
            bw.flush();
            bw.close();
            return ;
        }

        int count = 0;

        while(!boxes.isEmpty()) {

            int index = 0;

            for (int i = 0; i < cranes.size();) {
                if(index == boxes.size()) break;
                if (cranes.get(i) >= boxes.get(index)) {
                    boxes.remove(index);
                    i++;
                }else {
                    index++;
                }
            }
            count++;
        }

        bw.write(String.valueOf(count));

        bw.flush();
        bw.close();
    }
}

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.