[JAVA] 스택/큐 Lv.2 / 다리를 지나는 트럭

[문제]

 

[입출력 예]

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

 

[제한 조건]

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

 

[알고리즘]

다리를 Queue로 만들어놓고 반복문으로 모든 트럭이 빠질때까지 반복문을 실행하고 조건을 걸어준다

• 1 .queue가 비어 있을 경우 (다리에 트럭이 없을 경우), 큐에 트럭의 무게를 넣는다
• 2.  큐의 크기가 다리의 크기와 같을 경우(트럭이 다리를 다 지났을 경우), 큐에서 꺼내 무게를 빼준다
     (Queue의 FIFO 성질 이용)
• 3. 큐가 비어있지 않고 , 다음 트럭의 무게를 더했을때 무게가 초과될 경우 , 큐에 0을 넣는다.
• 4. 큐가 비어있지 않고 , 현재 무게 + 다음 트럭 무게가 초과되지 않을 경우 , 큐에 다음 트럭의 무게를 넣는다.

[코드]

 

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;		//정답 (걸리는 시간)
        Queue<Integer> bridq = new LinkedList<>();  //다리 Queue
        int max = 0;    //무게 초과 판별 위한 변수
        for(int t : truck_weights){
            
            while(true){
            	//다리가 비어있을 경우
                if(bridq.isEmpty()){
                bridq.offer(t);
                max += t;	//트럭 무게 추가
                answer++;  
                break;		//다음 트럭을 실을지 말지 판별 위해 빠져나가는 break        
            }else if(bridq.size() == bridge_length){ 
            	//큐의 크기와 다리 길이가 같을때
                 max -= bridq.poll();   // 현재 무게에서 다리를 다 건넌 트럭 무게 빼낸다
                }else{
         
                    if(max+t > weight){
                    	//현재무게 + 다음 트럭 무게 > 다리 최대 무게인 경우
                        bridq.offer(0);		//큐에 0 추가
                        answer++;
                        }else{
                        	//현재 무게 + 다음 트럭무게가 다리 최대 무게를 초과하지 않을 경우
                            bridq.offer(t);	//큐에 다음 트럭 무게 추가
                            max += t;
                            answer++;
                            break;
                        }
                }
            
       		 }
          }
            
        return answer + bridge_length;		
    }
}