[프로그래머스] 다리를 지나는 트럭 ( java )

[프로그래머스] 다리를 지나는 트럭 ( 자바 )

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스

 

 

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

= 트럭이 다리에서 완전히 내리지 않은 경우도 이 트럭의 무게는 고려하지 않는다. 

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

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

 

 

 

핵심 

1. queue
   현재 다리 위에 올려져 있는 트럭들을 의미한다. 
   먼저 들어온 트럭이 먼저 나간다. 
   
   

2. endTime[i] i번째 트럭이 다리를 모두 지나는 시간
   트럭이 다리에서 완전히 내려야지만 트럭의 문제를 고려하게 된다.
   따라서, 'endTime[i]은 i번째 트럭이 다리에 완전히 올라간 시간 + 다리의 길이'가 된다.
   
   

3. 트럭 input/output 순서다리에서 제일 앞 트럭이 내린 후에 대기하는 트럭이 올라가야 한다. 

 

구조

for ( time = 1 ~ )  첫 번째 트럭이 일단 다리에 오른 상태부터 시작한다. 

    cur : 대기하는 트럭 중 제일 앞에 트럭 
    if ( 큐가 안비었고, 큐 첫 번째 트럭 endTime == time )

       큐.poll
       다리 버팀 무게 수정 

 

    if ( cur 무게 <= 다리가 버틸 수 있는 무게 )

       다리 버팀 무게 수정 

       cur의 endTime  = time + 다리 길이 

       cur++

 

    if ( 큐. empty )  cur를 종료 조건으로 두려고 했다. 하지만 그러면 마지막 이동 중인 트럭을 고려하지 않고 끝나게 된다. 

      종료 

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

 

코드

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int[] endTime = new int[truck_weights.length];
        
        Queue<Integer> onBridge = new LinkedList<Integer>();
        int time = 0, cur=0;
        while(true) {
            // 도착한 버스 제거 
            if(!onBridge.isEmpty() && endTime[onBridge.peek()] == time) {
                weight += truck_weights[onBridge.poll()];
            }
            
            // 대기하는 버스 추가 
            if(cur < truck_weights.length && truck_weights[cur] <= weight) {
                onBridge.add(cur);
                endTime[cur] = time + bridge_length;
                weight -= truck_weights[cur];
                cur++;
            }
            
            time++;
            if(onBridge.isEmpty())
                break;
        }
        return time;
    }
}