다리를 지나는 트럭

코딩테스트 문제

프로그래머스

 

문제 접근)
bridge_length 10^4, weight의 무게는 상관이 없으므로 생략, truck_weights는 10^4 이므로 10^8이므로 시간복잡도는 O(N)이하의 알고리즘으로 해결해야 합니다.

 

정답 및 해설

function solution(bridge_length, weight, truck_weights) {
    /*  
        대기 트럭들이 있고, 하나씩 다리를 건너며 먼저 건너는 트럭들이 먼저 다리를 지나므로 큐 알고리즘을 이용하여
        푸는 문제입니다.
        대기 트럭의 큐와 다리를 건너는 큐 두개의 큐를 이용한다고 생각하면 편한것 같습니다.
    */
    let time = 0; // 경과 시간
    let bridge_queue = Array(bridge_length).fill(0); // 다리위에 트럭을 표시하기 위해 0으로 셋팅 후 이후 하나씩 다리를 건널떄 마다 트럭 무게 추가
    
    while(bridge_queue.length) { // 다리를 건너는 트럭이 없을때 까지 반복
        time += 1; // 1초 증가
        bridge_queue.shift(); // 다리를 건너는 트럭에서 1초 증가했으므로, 트럭 1대가 추가됩니다.
        
        if (truck_weights.length) { // 대기 트럭이 있을 떄만 여러 트럭을 보낼 수 있는지 weight_sum 체크를 하므로 이조건 필요!
            let weight_sum = bridge_queue.reduce((prev, next) => prev + next, 0)
            if (weight_sum + truck_weights[0] <= weight) { // 현재 다리에 있는 무게 + 다음 트럭의 무게가 weight(버틸 수 있는 무게)를 벗어나지 않는지 체크
                bridge_queue.push(truck_weights.shift()); // 무게를 벗어나지 않으므로 대기 트럭 한대 이동
            } else { // 트럭을 한대 더 추가하면 무게를 벗어나므로 0으로 트럭 안보내게 
                bridge_queue.push(0);            
            }
        }
    }
    
    
    return time;
}

/* 예제 1의 결과값
{ bridge_queue: [ 0, 7 ], truck_weights: [ 4, 5, 6 ] }
{ bridge_queue: [ 7, 0 ], truck_weights: [ 4, 5, 6 ] }
{ bridge_queue: [ 0, 4 ], truck_weights: [ 5, 6 ] }
{ bridge_queue: [ 4, 5 ], truck_weights: [ 6 ] }
{ bridge_queue: [ 5, 0 ], truck_weights: [ 6 ] }
{ bridge_queue: [ 0, 6 ], truck_weights: [] }
{ bridge_queue: [ 6 ], truck_weights: [] }
{ bridge_queue: [], truck_weights: [] }
*/