1092번 : 배 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공(1시간 9분)

아이디어

사실 단순 그리디로도 풀 수 있는 문제이지만 처음에 그렇게 짰다가 틀리고 나서 이분탐색을 이용해서 풀어주었다.
깔끔한 코드랑은 거리가 있으나 이렇게도 풀구나~ 또는 나도 이분탐색으로 풀었다는 사람들을 위해 올린다.

 

내 아이디어는 이러하다.

 

크레인과 박스를 각각 오름차순 정렬한다. 박스는 무거운 것부터 처리하기 위해 뒤에서부터 탐색한다. 매 라운드마다 모든 크레인은 동시에 움직일 수 있고, 한 번에 한 개의 박스만 옮길 수 있으므로 각 라운드를 시뮬레이션한다.

 

각 라운드에서는 아직 옮기지 않은 박스들을 무거운 순서로 살피면서, 현재 박스를 옮길 수 있는 크레인을 이분 탐색으로 찾는다. 조건은 크레인의 무게 제한이 박스 무게 이상이어야 하고, 이번 라운드에서 아직 사용되지 않은 크레인이어야 한다. 가능한 크레인 중 가장 적절한(무게 제한이 박스보다 크거나 같은 최소한의 크레인)을 선택한다.

 

이분 탐색은 크레인 배열이 오름차순이므로, left와 right를 좁혀가며 크레인 무게 제한이 박스보다 크거나 같은 구간을 찾는다. 해당 구간에서 아직 사용되지 않은 크레인을 발견하면 flag를 true로 설정하고 그 인덱스를 이번 라운드에 사용할 크레인으로 지정한다.

 

사용된 크레인은 used 배열에 표시하여 같은 라운드에서 중복 사용을 막는다.

 

한 라운드에서 박스를 옮길 수 있으면 박스를 -1로 표시하고, 누적 개수를 증가시킨다. 만약 한 라운드 동안 단 하나의 박스도 옮기지 못했다면 더 이상 진행할 수 없으므로 -1을 출력하고 종료한다.

 

모든 박스가 옮겨질 때까지 라운드를 반복하고, 누적된 라운드 수가 곧 최소 시간이다. 이 방식은 무거운 박스를 먼저 처리하므로 큰 크레인을 우선 배정하고, 이후 작은 박스들이 남은 크레인으로 처리될 수 있어 효율적이다. 정렬과 이분 탐색을 결합한 그리디 시뮬레이션 구조이다.

풀이코드

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int [] cranes = new int[N];
        for(int i=0; i<N; i++){
            cranes[i] = Integer.parseInt(st.nextToken());
        }
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int [] boxes = new int[M];
        for(int i=0; i<M; i++){
            boxes[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(boxes);
        Arrays.sort(cranes);
        int time = 0, cnt = 0;
        while (cnt!=M){
            time++;
            boolean [] used = new boolean[N];
            int usedCraneCnt = 0;
            for(int i=M-1; i>=0; i--){
                int left = 0;
                int right = N-1;
                int mid= (left+right)/2;
                int thisRound = mid;
                boolean flag= false;
                if(usedCraneCnt>=N){
                    break;
                }
                if(boxes[i]==-1){
                    continue;
                }
                while (left<=right){
                    mid = (left+right)/2;
                    if(cranes[mid]>=boxes[i]){
                        if(!used[mid]){
                            left = mid+1;
                            flag = true;
                            thisRound = mid;
                        }
                        else{
                            right = mid-1;
                        }
                    }
                    else{
                        left = mid+1;
                    }
                }
                if(flag){
                    used[thisRound] = true;
                    boxes[i] = -1;
                    cnt++;
                    usedCraneCnt++;
                }
            }
            if(usedCraneCnt==0){
                System.out.print(-1);
                return;
            }
        }
        System.out.print(time);
    }
}