문제

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

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

제한사항

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

입력

bridge_length : 2
weight : 10
truck_weights : [7,4,5,6]

출력

8

내가 했던 풀이 방법

문제를 풀기 전에 프로그래머스 문제에서 제대로 설명되지 않은 부분이 있어서 원본 문제로 풀이 방법을 설명하고자 한다. 문제에서는 bridge_length를 단순히 다리에 올라갈 수 있는 트럭 수를 의미했는데, 원본 문제에서는 해당 문제를 단위 길이로 표시했고, 각 트럭들은 하나의 단위시간에 하나의 단위길이만큼 이동할 수 있다고 가정한다고 적혀있다. 즉, bridge_length는 다리에 올라갈 수 있는 트럭의 수도 되지만, 트럭이 건너기까지 걸리는 시간이 될 수도 있다.

1. bridge를 bridge_length 크기만큼을 0으로 채워준다. 여기서 0은 현재 bridge에 있는 트럭의 무게들을 나타내게 된다. 처음에는 아무 트럭도 없으므로 모두 0이다.
2. currentWeight는 다리에 올라와있는 트럭의 무게이고 truckIndex는 truck_weights를 다루기 위한 index이다.
3. truckIndex가 truck_weights가 되는 경우, 더 이상의 트럭이 존재하지 않다는 의미이므로 반복을 중단해야 한다. 다만, 다리를 지나가는 트럭이 있을 수 있으므로 currentWeight가 0이 되기 전까지는 반복을 유지해야 한다. 반복을 한 번 진행할 때마다 time이 증가하고 bridge의 맨 앞 요소가 제거되고 currentWeight에서 해당 트럭의 무게를 빼준다.
4. 올라갈 수 있는 트럭이 아직 존재하고, 현재 다리 위 트럭의 무게의 합에서 다음으로 올라갈 트럭의 무게가 최대로 버틸 수 있는 무게보다 작다면, bridge에 해당 트럭을 올려주고, currentWeight에 해당 트럭에 무게를 추가해준다. 해당 트럭이 다리에 올라갔으므로 truckIndex도 1 증가시켜주어야 한다.
5. 만약 무게가 넘어가 트럭이 올라갈 수 없다면 bridge에 0을 추가해주어 아무 트럭도 올라가지 않았음을 나타내준다.
6. 3~5번이 끝난 뒤 time을 return 해준다.

코드

function solution(bridge_length, weight, truck_weights) {
    let time = 0;
    let bridge = Array.from({length: bridge_length}, ()=>0);
    let currentWeight = 0;
    let truckIndex = 0;
    
    while(truckIndex < truck_weights.length || currentWeight > 0) {
        time++;
        currentWeight -= bridge.shift();
        
        if(truckIndex < truck_weights.length) {
            if(currentWeight+truck_weights[truckIndex] <= weight) {
                bridge.push(truck_weights[truckIndex]);
                currentWeight += truck_weights[truckIndex++];
            } else {
                bridge.push(0);
            }
        }
    }
    
    return time;
}

회고

처음에는 Map을 이용해서 풀이하려고 했다. queue로 풀이해야 하는 건 알았으나... queue로 풀이하게 되면 shift를 써야할 것 같았고 그럼 분명 시간 초과에서 문제가 생길 것 같았다. 트럭이 다리에 올라가서 일정 시간 뒤에 제거되어야 하기 때문에 그 부분을 관리하기 위해 queue 대신 Map으로 하려고 했으나 코드가 너무 복잡해질 것 같아서 보니 shift로도 충분히 풀이가 가능했다......... 항상 안 될거 알면서도 시도했는데 왜 오늘은 시도를 안 했나 몰라...