[JS] 다리를 지나는 트럭

 

 

난이도: Lv. 2

정답률: 53%

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

 

 

알고리즘

트럭이 다리에서 내려오는 시점은 (다리에 올라간 시각 + 다리의 길이)이다.

대기 트럭이 없을 때까지 아래의 과정을 반복한다.

1. 시간을 1 증가시키고, 다리 위에 트럭이 존재한다면 현재 시각과 트럭이 다리에서 내려오는 시각이 일치하는지 확인한다. 일치한다면 다리 위에 있는 트럭들을 나타내는 큐에서 dequeue 한다.
2. 다리 위에 트럭이 더 올라갈 수 있는지 확인한다. 첫 번째 조건은 최대 트럭 수를 넘지 않는가이고, 두 번째 조건은 이 트럭이 다리에 올라갔을 때 다리가 견딜 수 있는 최대 무게를 넘지 않는가이다. 두 조건 모두 충족한다면 트럭을 다리에 올린다.

트럭을 모두 다리에 올렸다면(대기 트럭이 존재하지 않으면) 현재 다리 위에 있는 트럭들이 언제 내려오는지 계산해야 한다. 따라서 다리 위에 있는 트럭이 모두 내려올 때까지 위에서 서술한 1번 과정을 반복한다.

 

 

코드

function solution(bridge_length, weight, truck_weights) {
    let answer = 0;
    let truckNum = 0;
    const onBridge = [];

    // 대기 트럭이 없을 때까지 반복
    while (truckNum < truck_weights.length) {
        answer++;

        // 다리를 지난 트럭
        onBridge.length && bridge_length + onBridge[0]['startTime'] === answer && onBridge.shift();

        // 다리에 트럭 올리기
        const sum = onBridge.reduce((acc, currValue) => acc + currValue['weight'], 0);
        if (sum + truck_weights[truckNum] <= weight && onBridge.length + 1 <= bridge_length) {
            onBridge.push({ weight: truck_weights[truckNum], startTime: answer });
            truckNum++;
        }
    }

    // 다리를 건너고 있는 트럭이 없을 때까지 반복
    while (onBridge.length) {
        answer++;
        bridge_length + onBridge[0]['startTime'] === answer && onBridge.shift();
    }

    return answer;
}

 

 

주저리

코테 문제 한 2~3주 만에 푼 것 같은데 너무 오랜만에 풀어서 그런지 시간이 좀 걸렸다. 카테고리 분류 안되어있었으면 더 오래 걸렸을 수도.......