백준 1092 배 java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/1092

1. 크레인과 박스에 무게가 존재한다.

2. 크레인은 자신보다 무거운 박스를 들 수 없다.

3. 모든 크레인은 한 번에 하나의 박스밖에 운반하지 못하고, 자신보다 가벼운 박스를 옮기는데 무조건 1분이 든다.

2. 코드가 나오기까지 🛠️

(1) 시간복잡도 분석 ⏳

3. 코드 🌐

(1) SUDO CODE 💬

1. 1분부터 10,000분까지를 기점으로 이분 탐색하기 (start = 1, end = 10,000)
2. 현재 찾은 mid 값으로 모든 박스를 옮길 수 있는지 체크
   (1) 되면 mid 하향 조정
   (2) 안되면 mid 상향 조정
3. start의 위치가 바로 답이다.

(2) JAVA CODE ☕

import java.util.*;
import java.io.*;
 // b 17255 N으로 만들기
public class Main {
    static int N,M;
    static ArrayList<Integer> cranes = new ArrayList<>();
    static ArrayList<Integer> boxes = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            cranes.add(Integer.parseInt(st.nextToken()));
        }        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++){
            boxes.add(Integer.parseInt(st.nextToken()));
        }        cranes.sort(Collections.reverseOrder());
        boxes.sort(Collections.reverseOrder());
        System.out.println(binary_search());
    }
    public static int binary_search(){
        int start = 0;
        int end = 10_001;
        while (start <= end){
            int mid = (start + end)/2;
            if(isRight(mid)) end = mid-1;
            else start = mid+1;
        }        return start > 10_001 ? -1 : start;
    }
    public static boolean isRight(int round){
        int cnt = 0;
        boolean [] isVisited = new boolean[M];
        for(int k = 0; k < round; k++){
            int j = 0;
            for(int i = 0; i < N; i++){
                int now_crane = cranes.get(i);
                while ( j < M && (boxes.get(j) > now_crane || isVisited[j])) j++;
                if( j < M && boxes.get(j) <= now_crane) {
                    isVisited[j] = true;
                    cnt++;
                }            }            if(cnt == M) return true;
        }//        System.out.printf("round: %d,%s\\n", round, Arrays.toString(isVisited));
        return false;
    } }

4. 트러블 슈팅 or 배운 점📝

(1) 우선순위 큐 풀이 했다가 시간초과남.

import java.util.*;
import java.io.*;
 // b 17255 N으로 만들기
public class Main {
    static int N, M;
    static ArrayList<Integer> cranes = new ArrayList<>();
    static PriorityQueue<Integer> boxes = new PriorityQueue<>((a,b) -> b-a);
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            cranes.add(Integer.parseInt(st.nextToken()));
        }
        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i <M; i++){
            int now =Integer.parseInt(st.nextToken());
            boxes.add(now);
        }

        cranes.sort(Collections.reverseOrder());

        int time = 0;

        ArrayList<Integer> temp = new ArrayList<>();
        while (!boxes.isEmpty()){
            for(int i = 0; i < cranes.size(); i++){
                int now_crane = cranes.get(i);
                if(i == 0 && !boxes.isEmpty() && now_crane < boxes.peek()) {
                    System.out.println(-1); // 첫 타자인데, 가장 무거운 크레인보다 무거우면 못 듦 -> 그냥 나가기
                    return;
                }
                while (!boxes.isEmpty() && now_crane < boxes.peek()){
                    int now_box = boxes.poll();
                    temp.add(now_box);
                }
                if(!boxes.isEmpty() && now_crane >= boxes.peek()) boxes.poll();
            }
            time++;
            boxes.addAll(temp);
            temp.clear();
        }
        System.out.println(time);
    }
 }

(2) 투 포인터 쓰면 더 쉬움

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

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());
        List<Integer> cranes = new ArrayList<>();

        String[] tokens = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            cranes.add(Integer.parseInt(tokens[i]));
        }
        cranes.sort((o1, o2) -> o2 - o1);

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

        tokens = br.readLine().split(" ");
        List<Integer> boxs = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            boxs.add(Integer.parseInt(tokens[i]));
        }
        boxs.sort((o1, o2) -> o2 - o1);
        int result = move(cranes, boxs);

        System.out.println(result);
    }

    private static int move(List<Integer> cranes, List<Integer> boxs) {
        int count = 0;

        if (cranes.get(0) < boxs.get(0)) {
            return -1;
        }

        while (!boxs.isEmpty()) {
            count++;

            int craneIndex = 0;
            int boxIndex = 0;

            while (craneIndex < cranes.size()) {
                if (boxIndex >= boxs.size()) {
                    break;
                }
                if (cranes.get(craneIndex) >= boxs.get(boxIndex)) {
                    boxs.remove(boxIndex);
                    craneIndex++;
                } else {
                    boxIndex++;
                }
            }
        }

        return count;
    }
}

• iterator 가 가리키고 있지 않은 쪽을 삭제

• for-each 문에서 값을 즉시 삭제