다리를 지나는 트럭

문제 

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

bridge_length	weight	truck_weights	return
2	10	7,4,5,6	8
100	100	10	101
100	100	10,10,10,10,10,10,10,10,10,10	110

 

풀이 

1. 브릿지 길이가 2라면 트럭 하나가 지나는 시간은 2초임 

2. 브릿지 길이 만큼 queue에 넣고 빼는 과정을 해야함 

3. 이는 무한히 가능할 수 있으므로 while을 true로 하고 break 하는 방식으로 진행 

 

public static int solution(int bridge_length, int weight, int[] truck_weights){

	int answer=0;
    int truckSum =0;
    Queue<Integer> queue = new LinkedList<>();
    
    for(int i=0; i<truck_weights.length; i++){
    	int truck = truck_weights[i];
        
        while(true){
        	if(queue.isEmpty()){ //브릿지에 없으면 트럭 추가 
            	queue.add(truck);
                truckSum = truck;
            	break;
            }else if(queue.size() == bridge_length){ // 브릿지가 포화면 트럭 제거 
            	truckSum -= queue.poll();
                
            }else{
            	if(truckSum + truck <= weight){ //다음 트럭을 실을 수 있으면 트럭 추가 
					queue.add(truck);
                    truckSum+=truck;
					break;
                }else{ // 다음 트럭을 실을 수 없다면 0을 실어서 포화 상태로 만들어서 다음 뎁스에 탈출  
                	queue.add(0);
                    answer++;
                }
            }
        }
    }
    
    return answer + bridge_length; 
}