[백준] 1092번 배 (자바 풀이)

문제

https://www.acmicpc.net/problem/1092

1092번: 배

풀이

이 문제는 간단한 정렬과 그리디 알고리즘을 적용하여 풀 수 있다. 

 

먼저 크레인과 박스를 내림차순으로 정렬한다. 

이후 크레인과 박스를 순차적으로 대조하여 옮길 수 있다면 박스 리스트에서 박스를 제거한다.

 

간단한 방법이지만, 자료구조를 어떤 것을 사용하냐에 따라서 시간초과가 발생할 수 있다.

나는 처음에는 box를 제거할 때 시간이 O(1)밖에 걸리지 않는 LinkedList 자료구조를 사용했다.

하지만 LinkedList는 원소 접근에 O(n)의 시간이 걸리기 때문에 시간초과가 발생한다.

제거보다는 원소 접근을 더 많이 하므로 ArrayList를 이용하여 풀어야 시간초과가 발생하지 않는다.

코드

import java.util.*;
import java.io.*;
 
public class Baekjoon_1092 {
    static int N,M;
    static ArrayList<Integer> crane;
    static ArrayList<Integer> box;
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        crane = new ArrayList<>();
        for(int i=0; i<N; i++) {
            crane.add(sc.nextInt());
        }
        M = sc.nextInt();
        box = new ArrayList<>();
        for(int i=0; i<M; i++) {
            box.add(sc.nextInt());
        }
        
        Collections.sort(crane, Collections.reverseOrder());
        Collections.sort(box, Collections.reverseOrder());
        
        if(box.get(0) > crane.get(0)) {
            System.out.println(-1);
            return;
        }
        
        int ans = 0;
    
        while(!box.isEmpty()) {
            int idx =0;
            for(int i=0; i< N; ) {
                if(idx == box.size()) break;
                else if(crane.get(i) >= box.get(idx)) {
                    box.remove(idx);
                    i++;
                }else idx++;
            }
            ans++;
        }
        
        System.out.println(ans);
                
    }
 
}

결과

여러가지 실험해보느라 결과가 이렇다 ㅋㅋㅋ