[JAVA]1092 배 ( 이분 탐색 )

 📚 문제  

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

🔍 아이디어  

크래인을 효율적으로 사용하는 것이 중요하다고 생각했습니다.

한 크래인이 실을 수 있는 물건들중 가장 무거운 물건을 선택한다면 가장 효율적으로 크래인을 사용하여 모든 화물을 실을 수 있을것이라 판단하여 이분 탐색을 이용하여  크래인이 실을 수 있는 무게 N보다 작은 수중 가장 큰 숫자를 선택했습니다. 

 

-1이 나오는 경우는 크래인의 옮길 수 있는 가장 큰 허용량 보다 무거운 화물이 있는경우이기에 sort를 이용하여 정렬후에 비교하였습니다.

 

이분탐색에서 어떤 한 숫자보다 작은 수중에 가장 큰 수는  아래와 같은 로직으로 해결할 수 있습니다

crane이 실을 수 있는 경우 result를 갱신합니다.

//이분탐색은 정렬되어있어야 한다.
//작은것중 가장 큰것
private static int findMaxLower(int nowCrane) {
    int start = 0;
    int end = cargos.size() - 1;
    int result = -1; //작은것중에 가장 큰 값

    while (start <= end) {
        int mid = (start + end) >> 1;
        if (cargos.get(mid) <= nowCrane) {
            result = mid; //작은것을 저장한다.
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return result;
}

 

📝 풀이 

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

public class Main {
    private static final List<Integer> cargos = new ArrayList<>();

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

        int craneCnt = Integer.parseInt(br.readLine());
        List<Integer> cranes = new ArrayList<>();

        //input
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < craneCnt; i++) {
            int now = Integer.parseInt(st.nextToken());
            cranes.add(now);
        }

        int cargoCnt = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < cargoCnt; i++) {
            cargos.add(Integer.parseInt(st.nextToken()));
        }

        //sort
        Collections.sort(cranes);
        Collections.sort(cargos);

        //solution
        if (cranes.get(craneCnt - 1) < cargos.get(cargoCnt - 1)) System.out.println(-1); //크래인이 실을 수 있는 무게보다 무거움
        else {
            int cnt = 0;
            while (!cargos.isEmpty()) {
                cnt++;
                for (int i = 0; i < craneCnt && !cargos.isEmpty(); i++) {
                    removeCargo(cranes.get(i));
                }
            }
            System.out.println(cnt);
        }
    }

    private static void removeCargo(int nowCrane) {
        int idx = findLower(nowCrane);
        if (idx != -1) {
            //해당 크래인으로 옮길 수 있는 화물이 있는 경우
            cargos.remove(idx);
        }
    }

    //작은것중 가장 큰것
    private static int findMaxLower(int nowCrane) {
        int start = 0;
        int end = cargos.size() - 1;
        int result = -1; //작은것중에 가장 큰 값

        while (start <= end) {
            int mid = (start + end) >> 1;
            if (cargos.get(mid) <= nowCrane) {
                result = mid; //작은것을 저장한다.
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return result;
    }
}