백준 1092번 배

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Ship {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] crane = new int[N];
        for (int i = 0; i < N; i++) {
            crane[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            int box = Integer.parseInt(st.nextToken());
            list.add(box);
        }
        Arrays.sort(crane);
        Collections.sort(list);
        int time =0;
        int boxIndex = M-1;
        if(crane[N-1]<list.get(boxIndex)){
            System.out.println(-1);
            return;
        }
        loop: while (true){
            time++;
            boxIndex = list.size()-1;
            for (int i =N-1; i >=0; i--) {
                if(crane[i]>=list.get(boxIndex)){
                    list.remove(boxIndex);

                    boxIndex--;
                    if(list.size()==0&&boxIndex==-1) break loop;
                    if(list.size()!=0&&boxIndex==-1) break;
                }
                else {
                    boxIndex--;
                    i++;
                    if(boxIndex==-1) break;
                }

            }
        }
        System.out.println(time);
    }
}

풀이방법

📢 우선 이 문제는 제한무게(crane)과 박스 무게(box)를 둘다 정렬해줘야 한다는 것 까지는 쉽게 생각할 수 있다.

이제 박스를 크레인과 하나씩 매칭시켜 주는데, 값이 큰것부터 순차적으로 crane[i]>=list.get(boxIndex) 해준다.
이조건에 안맞을때의 처리가 이문제의 핵심 포인트다.
조건에 맞지 않을때, 시간을 증가시키고, 크레인의 큰것부터 다시 탐색하기 쉬운데, 그렇게 로직을 구성하면 반례에 걸린다.

반례:
제한 무게: 1 2
박스 무게: 1 1 2 2

조건에 안맞을때, 시간을 증가시키는것이 아니라, 그다음 박스 무게를 탐색해서, crane[i]>=list.get(boxIndex) 이조건에 맞출수 있는지를 확인해야 한다.

1. 정렬 후, 제한무게 보다 큰 박스무게 값이 있을 경우 -1처리해준다.
2. 값이 큰것부터 크레인과 박스를 하나씩 매칭시키는데, 조건에 맞을 경우 list에 담은 박스 값을 제거한다.
3. 크레인의 처음부터 탐색시, 시간을 증가시키고, boxIndex에 남은 박스의 개수-1을 넣는다.
4. list에 남은게 있는데 boxIndex가 -1이 되는경우엔 시간을 증가시키고, 크레인의 처음부터 다시 탐색한다.
5. 조건에 맞지 않는다면, 해당 크레인 값에 맞는 다른 박스가 있는지 더 확인해본다. 없다면, 3번으로 돌아간다.

후기

반례조건만 잘 찾는다면 쉽게 해결할 수 있는 문제였는데, 내가 정교하게 처리하지 못해서 질문게시판의 반례를 참고했다.
혼자 해결한게 아니라 아쉬움이 남는 문제다