[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1092번, 배

문제 링크

1092번: 배

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 각 크레인은 1분에 하나의 박스를 옮기며, 무게 제한보다 무거운 박스를 드는 순간 움직일 수 없습니다.

2. 모든 박스를 옮길 때 최소 시간을 결과로 출력합니다.

3. 모든 박스를 옮길 수 없을 때 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 크레인과 박스를 무게 기준으로 정렬한 뒤, 무거운 박스부터 옮기기를 진행합니다.

 

3. 모든 박스를 옮길 수 있으면 시간, 못 옮기면 -1을 결과로 출력합니다.

 

 

모든 박스 옮길 수 있는지 확인하기.

 

모든 박스를 옮기려면 모든 박스가 크레인의 무게 제한보다 작아야 합니다.

 

 

 

결과적으로 크레인 중에 무게 제한 최대값보다 큰 박스가 존재하면 박스를 모두 옮길 수 없습니다.

 

"크레인 최대 무게 제한 값 < 박스의 무게" 일 때

 

박스를 모두 옮길 수 없으므로 -1을 결과로 출력합니다.

 

 

크레인으로 박스 옮기기.

 

모든 박스를 옮길 수 있을 때 크레인으로 박스 옮기기를 진행합니다.

 

최소 시간으로 모든 박스를 옮기려면 각 크레인이 박스를 옮길 때

 

무게제한의 가장 가까운 박스부터 옮기는 것을 반복하면 됩니다.

 

예를 들어.

 

크레인 : 1 2 3 4

박스 : 1 1 2 2 3 3 4 4

 

1 → 12 → 23 → 34 → 4

 

2번 반복하면 모든 박스를 옮길 수 있습니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N = 3

 

크레인

크레인 1	크레인 2	크레인 3
6	8	9

M = 5

 

박스

박스 1	박스 2	박스 3	박스 4	박스 5
2	5	2	4	7

 

2. 크레인과 박스를 무게 기준으로 정렬한 뒤, 무거운 박스부터 옮기기를 진행합니다.

 

크레인 내림차순 정렬!

 

크레인 3	크레인 2	크레인 1
9	8	6

크레인 최대 무게 제한 : 9 

 

박스 오름차순 정렬!

 

박스 1	박스 3	박스 4	박스 2	박스 5
2	2	4	5	7

 ※모든 박스의 무게는 크레인 최대 무게 제한보다 작으므로 모든 박스를 옮길 수 있습니다.

 

박스 옮기기

 

박스 1	박스 3	박스 4	박스 2	박스 5
2	2	4	5	7

 

크레인 3 → 박스 5

크레인 2 → 박스 2

크레인 1 → 박스 4

 

박스 1	박스 3
2	2

 

크레인 3 → 박스 3

크레인 2 → 박스 1

 

모든 박스 옮기기 성공!

 

3. 모든 박스를 옮길 수 있으면 시간, 못 옮기면 -1을 결과로 출력합니다.

 

모든 박스를 옮기는 것이 가능하기 때문에 최소 시간 : 2초

 

 

2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenzier를 이용하여 박스와 크레인에 무게 관련 정보를 띄어쓰기 기준 나누었습니다.
• Collections.sort와 List.sort를 이용해서 크레인과 박스 무게에 대한 정보 기준 정렬하였습니다.
• 박스를 모두 옮길 수 있으면 박스 옮기기를 진행하여 최소 시간을 구합니다.
• 박스를 모두 옮기는 여부에 따라서 최소 시간, -1을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.*;

public class Main{
    static int N, M;
    static ArrayList<Integer> crane = new ArrayList<>();	//크레인 무게 제한 정보 리스트
    static ArrayList<Integer> box = new ArrayList<>();	//박스 무게 정보 리스트
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        boolean check = true;
        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine()," ");
        int max = -1;
        //크레인 무게 제한 저장 및 최대 무게 제한 구하기
        for(int i=0;i<N;i++){
            crane.add(Integer.parseInt(st.nextToken()));
            max = Math.max(max, crane.get(i));
        }
        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine()," ");
        //박스 무게 저장
        for(int i=0;i<M;i++){
            box.add(Integer.parseInt(st.nextToken()));
            //크레인 최대 무게 제한보다 큰 박스일 때
            // = 모든 박스 옮길 수 없음!
            if(box.get(i) > max){	
                check  = false;
                bw.write("-1");
                break;
            }
        }
        //모든 박스 옮길 수 있을 때
        if(check){
            crane.sort(Collections.reverseOrder());	//크레인 무게 제한 내림차순 정렬
            Collections.sort(box);	//박스 무게 오름차순 정렬
            int answer = 0;
            //cur = 크레인 인덱스, index = 박스 인덱스
            int cur = 0, index = M-1;
            //박스 옮기기 진행
            while(!box.isEmpty()){
                //현재 크레인 옮기기 성공!
                if(box.get(index) <= crane.get(cur)){
                    box.remove(index);	//해당 박스 제거!
                    cur++;	//크레인 인덱스 증가!
                }
                index--;	//박스 인덱스 감소
                //박스 옮기기 1 싸이클 진행시!
                if(cur == N || index == -1){
                    //박스와 크레인 인덱스 초기화
                    cur = 0;
                    index = box.size()-1;
                    answer++;	//1초 증가~
                }
            }
            bw.write(answer + "");	//최소 시간 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}