백준 [java 자바] 1092 : 배

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

1092번: 배

배들이 한번에 적재 할 수 있는 최대 무게가 나와있는 상태에서, 주어진 상자를 옮길 수 있는 시간의 최솟값을 구하는 문제이다. 

 나는 현재 남은 화물들을 차례대로 배에 실으면서 시간을 재는 방법을 선택했다.

 

처음에는 우선순위큐를 사용하려고 했으나, 최대무게를 저장해놓은 배열과 비교하는 과정에서 훨씬 복잡해질 것 같아서 linkedlist를 사용했다. 

그리고 시간을 최소화 하기 위해서 현재까지 흘러간 시간을 변수로 놓고 쟀고, 배열을 정렬하여 제한값이 큰 배부터 탐색하며 만약 더이상 실을 수 있는 상자가 없는 것을 때에는 그냥 break를 하였다.(뒤에 있는 배들은 실을 수 있는 무게가 더 적으므로 볼 필요가 없기 때문) ( 이부분을 하지 않아서 시간초과가 났었다.) 또한 화물도 정렬을 해서 최대한 큰 화물부터 옮기도록 하였다.

 

느낀점 : 앞으로 시간초과가 났을 때 시간복잡도 계산할 때를 생각하면서 어디서 시간이 많이 걸리는지 찾아야겠다.

 

풀이코드

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


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());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[n];

        for(int i = 0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());



       LinkedList<Integer> list = new LinkedList<>();

        for(int i = 0;i<m;i++){
           int k =Integer.parseInt(st.nextToken());
           if(k > arr[n-1]){
               System.out.println(-1);
               System.exit(0);
           }
           list.add(k);
        }

        Collections.sort(list);



        int ans = 0;

        while(list.size() != 0){
            ans++;

            for(int i = n-1;i>=0;i--){
                int now = arr[i];

                if(now < list.get(0)) break;

                for(int j = list.size()-1;j>=0;j--){
                    if(list.get(j) <= now){
                        list.remove(j);
                        break;
                    }
                }

                if(list.size() == 0) break;

            }
        }

        System.out.println(ans);




    }
}