JuSeok

1092번

문제

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

문제 해결 순서

  1. 처음 아이디어가 맞았는데 while문 안에 크레인이랑 박스 개수만큼 이중 for문을 돌아서 시간초과남.
  2. while문 하나로 idx(크레인 카운트), tmp(박스 카운트) 두개를 컨트롤 하는게 포인트.
  3. 추가적으로 처음엔 박스의 무게를 1000001로 바꿔서 옮김을 체크했는데 박스를 리스트로 바꿔 옮긴 박스는 삭제해버림.
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> craneList = new ArrayList<>(); // 크레인 중량
        ArrayList<Integer> boxList = new ArrayList<>(); // 박스 무게
        //1. 입력
        int n = sc.nextInt(); //크레인 갯수
        for(int i = 0; i < n; i++) {
            int a = sc.nextInt();
            craneList.add(a);
        }
        int m = sc.nextInt();//박스 갯수
        for(int i = 0; i < m; i++) {
            int a = sc.nextInt();
            boxList.add(a);
        }
        //2. 내림차순 정렬
        Descending descending = new Descending();
        Collections.sort(craneList, descending);
        Collections.sort(boxList, descending);
        int time = 0;//걸린 시간
        //3. 가장 무거운 박스의 무게 > 크레인 최대 중량일 경우
        if(boxList.get(0) > craneList.get(0))
            System.out.println("-1");
            //4. 그 외의 경우, 그리디 알고리즘
        else{
            while(boxList.size() != 0){
                int idx = 0;
                int tmp = 0;
                while(idx < n){
                    // 박스를 다 옮겼으면
                    if(tmp == boxList.size())
                        break;
                    // 박스를 옮길 수 있으면
                    if(boxList.get(tmp) <= craneList.get(idx)){
                        boxList.remove(tmp);
                        idx++;
                    }
                    // 박스를 옮길 수 없으면, 다음 박스
                    else if(boxList.get(tmp) > craneList.get(idx)){
                        tmp++;
                    }
                }
                time++;
            }
            System.out.println(time);
        }
        sc.close();
    }
}
class Descending implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

Tags