[백준/1092] 배 - JAVA

📌 문제

알고리즘 분류 : 그리디 알고리즘
난이도 : 골드5
출처 : 백준 - 배

🦧 문제 풀이 접근

그리디 알고리즘으로 문제를 해결한다.
boxArray와 craneArray를 정렬한다.
반복문을 통해 각각의 인덱스를 비교한다.
반복문 횟수를 출력한다.

💻 code

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());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int craneArr[] = new int[N];
        for(int i=0;i<N;i++)
            craneArr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(craneArr);
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine()," ");
        int boxArr[] = new int[M];
        for(int i=0;i<M;i++)
            boxArr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(boxArr);
        boolean check[] = new boolean[M];
        int cnt=0, boxCnt=0;
        while(true) {
            cnt++;
            int cp = N-1, bp = M-1;
            boolean flag = false;
            while(cp>=0 && bp>=0) {
                if(check[bp]) {
                    bp--;
                }
                else if(craneArr[cp]>=boxArr[bp]) {
                    check[bp] = true;
                    cp--;
                    bp--;
                    boxCnt++;
                    flag = true;
                }
                else if(craneArr[cp]<boxArr[bp]) {
                    bp--;
                }
            }
            if(!flag) {
                System.out.println(-1);
                return;
            }
            if(boxCnt==M)
                break;
        }
        System.out.println(cnt);
    }
}

🥇 결과

🎓 느낀점

그리디 알고리즘을 이용해 풀수있다. 반복문 탈출조건을 햇갈리지말자.