[자바] 백준 1092번: 배

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

1092번: 배

---

빨리 박스들을 다 옮기기 위해서

크레인은 자기가 들 수 있는 가장 무거운 박스를 옮겨야 한다.

.

.

 

 

크레인이 들 수 있는 무게를 내림차순으로 정렬

박스의 무게를 내림차순으로 정렬한다.

 

크레인 배열을 하나씩 순회하면서 들 수 있는 박스가 있으면 해당 박스를 든다(최대한 무거운거).

모든 크레인을 한번 씩 다 돌았으면 time을 1 증가시킨다.

 

다시 남아있는 박스들로 반복한다.

 

---

박스를 2차원배열로 만들어서 [i][0]인덱스에는 무게를, [i][1]인덱스에는 옮김 여부(1이면 옮겨야함, 0이면 이미 옮김)를 기록했다. 그런데 시간초과가 났다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class P1092 {

	public static void main(String[] args) throws IOException {


		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n= Integer.parseInt(br.readLine());
		
		Integer[] crane = new Integer[n];
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			crane[i]=Integer.parseInt(st.nextToken());
		}
		
		int m= Integer.parseInt(br.readLine());
		int[][] box= new int[m][2];
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<m;i++) {
			box[i][0]=Integer.parseInt(st.nextToken());
			box[i][1]=1;
		}

		Arrays.sort(crane, Collections.reverseOrder());
		Arrays.sort(box, new Comparator<int[]>() {
		    @Override
			public int compare(int[] o2, int[] o1) {
		    	 if(o1[0] == o2[0]) {
	                	 return o1[1] - o2[1];
		    	 }else {
		    		 return o1[0] - o2[0]; 
		    	 }
	           }
	        });

		int count=0;
		int time=0;
		while(count<m) {
			time++;
			int j=0;
			for(int i=0;i<n;i++) {
				
				while(j<m) {
					if(box[j][1]==1 && box[j][0]<=crane[i]) {
						//옮길 수 있다
						box[j][1]=0;
						count++;
						j++;
						break;
					}
					j++;
				}
				if(j==m)
					break;
			
			}
		}
		
		System.out.println(time);
	}

}

box를 LinkedList로 바꾸고, 박스를 옮기면 해당 박스를 delete하도록 바꿔보았다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class P1092 {

	public static void main(String[] args) throws IOException {


		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n= Integer.parseInt(br.readLine());
		
		Integer[] crane = new Integer[n];
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			crane[i]=Integer.parseInt(st.nextToken());
		}
		
		int m= Integer.parseInt(br.readLine());
		LinkedList<Integer> box = new LinkedList<>();
		
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<m;i++) {
			box.add(Integer.parseInt(st.nextToken()));
		}

		Arrays.sort(crane, Collections.reverseOrder());
		
		Collections.sort(box, Collections.reverseOrder());
	
		int count=0;
		int time=0;
		
		if(box.peek() > crane[0])
		{
			System.out.println(-1);
			return;
		}
		while(count<m) {
			time++;
			int next;
			Iterator<Integer> it = box.iterator();
			
			for(int i=0;i<n;i++) {
				
				while(it.hasNext()) {
					next=it.next();
					if(next <= crane[i]) {
						//들 수 있다.
						it.remove();
						count++;
						break;
					}
				}
				
			}
		}
		
		System.out.println(time);
	}

}

LinkedList로 바꿔서하니까 엄청 빨라져서 놀랐다....