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

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

프로그래머스

 

목차

• 문제
• 풀이
• 코드

문제

입력

bridge_length : 다리 길이 (정수)

weight : 다리에 최대로 올라갈 수 있는 무게 (정수)

truck_weights : 트럭의 무게가 적힌 정수 배열

 

출력

return : truck_weights의 트럭이 모두 다리를 걸렸을 때 걸리는 최소 시간 (정수)

 

제한사항

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

풀이

이 문제는 큐 자료 구조를 사용해서 푸는 문제이다. 문제에서도 알 수 있듯이 truck_weights는 앞에서부터 순서대로 다리에 올라가고 다리에 올라간 순서대로 트럭이 다리에서 내려온다. 선입선출, 즉 큐 자료 구조를 이용하는 문제이다.

 

이 문제를 단계별로 분해해 보면 다음과 같다.

1. 다리를 만든다. 다리 무게를 만든다.
2. 트럭을 올린다. 다리 무게를 갱신한다.
3. 올라갈 트럭을 올릴지 말지 결정한다.
   올린다. 다리 무게를 갱신한다. / 올리지 않는다면 다리 위에 있는 모든 트럭을 한 칸 앞으로 이동시킨다.
4. 다리 가장 앞부분에 트럭이 있다면 트럭을 내린다. 다리 무게를 갱신한다.

이 때 어떤 것을 반복하느냐에 따라 while문, for...of, forEach문을 결정할 수 있는데 지금은 다리 무게가 기준이므로 do...while문을 사용하였다. while문을 사용하면 맨 처음 다리 무게가 0이므로 바로 종료된다.

 

이렇게 코드를 만든 후에 반복되는 것은 do...while문의 앞으로 그리고 줄일 수 있다면 continue 구문을 사용해서 좀 더 깔끔하게 만들었다. 그러나 기본적인 구조는 위의 단계를 따른다.

 

시간 복잡도는 최악의 경우를 생각해보면 모든 트럭이 따로따로 다리를 건너는 경우이므로 O(n)이다.

공간 복잡도는 truck_weights 배열과 다리 배열이므로 O(n)이다.

 

코드

function solution(bridge_length, weight, truck_weights) {
    var answer = 0;
    const bridge = new Array(bridge_length).fill(0);
    let weights = 0;
    
    do {
        answer++;
        weights -= bridge.shift();
        if (truck_weights.length) {
            const truck_weight = truck_weights[0];
            if (weight >= weights + truck_weight) {
                weights += truck_weight;
                bridge.push(truck_weights.shift());
                continue;
            } 
        }
        bridge.push(0);
    } while (weights);
    return answer;
}

 

2회독이니까 확실히 빨리 푼다. 여러 번 보자.

다리 길이가 많이 긴 경우 시간 복잡도를 줄이고 싶다. (어렵다. 3회독 때 고민하자.)

먼저 코드를 짜고 그다음에 중복을 제거하는 것이 가장 좋다. 이 방법 계속 고수하자. 예쁘다.