[프로그래머스] 스택 (stack) / 큐 (queue) _ 다리를 지나는 트럭

2021_08_15 알고리즘 스터디 문제 풀이

문제 URL : https://programmers.co.kr/learn/courses/30/lessons/42583?language=javascript 

코딩테스트 연습 - 다리를 지나는 트럭

 

문제

 

문제를 추론하는 과정에서 한 가지 이해가 어려웠던 게 있었는데, 트럭에 소요되는 시간에 대한 기준이었는데, 문제의 설명이 조금 부족하지 않았나 싶다.

문제의 인자로 주어지는 bridge_length 가 만약 2의 값을 가지고 있다면, 트럭 한대가 다리를 건너는 데에 드는 총 소요 시간도 bridge_length와 동일하다는 것을 이해하면 문제가 어렵지 않은 편인 것 같다.

 

수도코드

// requirement 
    // 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지
    // 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있음

// 트럭이 다리를 완전히 건너는 데에 드는 시간은 bridge_length초

// truck_weights[i]가 다리를 올라갈 수 있는 조건
    // 1. 현재 다리를 건너고 있는 트럭의 무게 + truck_weights[i]의 무게가 weight 이하
    // 2. 다리를 건너고 있는 트럭과 건너려고 하는 트럭의 갯수가 bridge_length 이하

// truck_weights[i]가 다리에 올라간 경우
    // 1. 대기 트럭에서 truck_weights[i]가 삭제 되어야 함
    // 2. bridge_length초만큼 올라가 있어야함 / 
    // 3. bridge_length를 초과한 경우 다리를 지난 트럭에 들어가야 함
   
// 대기 중인 트럭이 모두 다리를 지난 트럭에 들어가야 경과 시간 카운팅이 끝남 (while 문 조건은 다리를 지난 트럭이 초기 대기 트럭의 길이와 같을때까지)
// 다리를 건너는 트럭에 들어온 애는 bridge_length 만큼 머무르다가 경과 되었을 때 shift로 내보내고, 지난 트럭에 추가
// 와일문을 돌면서 0초부터 시작되는 second 변수를 사용,한다

수도코드를 제대로 작성하기 전에 필요 조건을 먼저 정리했다.

 

코드와 결합한 수도코드

// let second  = 0, 최종 결과로 사용할 second 변수 선언
// let onBridge = []; 
// let overBridge = [];
// while문 사용, 순회 조건은 onBridge.length가 0일때까지
    // 1. onBridge 배열에 이미 다 건넌 것들을 찾아서 필터링 해야 함
        // onBridge 배열을 순회, {truck: 7, second: 1}...
        // onBridge를 map으로 순회, second를 1씩 증가시킨다.
        // onBridge를 filter 매소드로 순회
            // second의 값이 bridge.length 이하인 것만 트루를 리턴한다
            // 그렇지 않은 경우, overBridge에 트럭을 넣어준다. 
        // 위 값을 onBridge에 재할당한다.
        // 
    // 2. 다리에 트럭을 추가 할 수 있는 지 확인
        // onBridge.length + 1을 한 값이 bridge_length 이하이고,
        // truck_weigths[0](무게) + onBridge 원소들의 합이 weight 이하인 경우
            // truck_weights.shift(), (맨 앞 요소를 제거하고)
            // 그 요소를 onBridge에 push로 추가한다/ {truck, second : 0}
            
    // 3. second를 1초 추가한다.
 // 최종적으로 second를 리턴한다

 

위의 수도코드를 참고하면 코드 작성에 문제가 없을 것이라고 판단, 코드 작성을 진행했다.

 

풀이

function solution(bridge_length, weight, truck_weights) {
    // while 문 순회조건을 충족하기 위해 트럭의 갯수를 저장
    const allTrucks = truck_weights.length;
    // 결과로 리턴할 소요 시간
    let second = 0;
    
    // 다리를 건너는 트럭
    let onBridge = [];
    
    // 다리를 지난 트럭
    let overBridge = [];
    
    while (overBridge.length < allTrucks) {
        // onBridge에서 이미 다 건넌 것들을 찾아서 필터링
        onBridge = onBridge.map((truck) => {
            // second 값을 1초씩 증가시킨다.
            truck.second = truck.second + 1;
            return truck;
        }).filter((truck) => {
            // second의 값이 bridge_length를 초과한 경우, 이미 다리를 지난 트럭, overBridge에 추가
            if (truck.second <= bridge_length) return true;
            overBridge.push(truck);
        })
        
        // 다리를 건너는 모든 트럭 무게의 합
        const allWeight = onBridge.reduce(((a, b) => a + b.truck
        ), 0);

        // 대기중인 첫번째 트럭
        const pendingTruck = truck_weights[0]
        
        // 다리에 트럭을 추가 할 수 있는 지 확인
        if (onBridge.length + 1 <= bridge_length && allWeight + pendingTruck <= weight) {
            const truck = truck_weights.shift();
            // 가능하다면 대기중인 트럭 배열에서 제거, onBridge에 추가한다.
            onBridge.push({truck , second: 1});   
        }
        second++;
    }
    return second;
}

시간 복잡도 : O(n^2)의 코드를 구현했다.