[프로그래머스] 다리를 지나는 트럭 - 자바스크립트

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다. 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

 

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

 

따라서, 모든 트럭이 다리를 지나려면 최소 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	weight	truck_weights	return
2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

 

풀이

스택&큐 파트의 문제

const solution = (bridge_length, weight, truck_weights) => {
    let time = 0;
    let bridge = {
        container: [],
        weight: 0,
        limitWeight: weight,
        length: bridge_length
    };
    let waiting_truck = truck_weights.map(truck => { return {weight: truck, position: null} });
    
    while(true){        
        bridge.container.forEach(truck => truck.position += 1)
        
        if(bridge.container.length > 0 && bridge.length - 1 < bridge.container[0].position){
            bridge.weight -= bridge.container[0].weight;
            bridge.container.shift();
        }
        
        if(waiting_truck.length !== 0 && bridge.container.length < bridge.length){
            if(bridge.limitWeight >= (bridge.weight + waiting_truck[0].weight)){
                waiting_truck[0].position = 0;
                bridge.container.push(waiting_truck[0])
                bridge.weight += waiting_truck[0].weight;
                waiting_truck.shift();
            }
        }
        
        time ++;
        if(waiting_truck.length === 0 && bridge.container.length === 0) break;
    }
    
    return time;
}

테스트 1 〉	통과 (0.76ms, 33.6MB)
테스트 2 〉	통과 (10.95ms, 36.8MB)
테스트 3 〉	통과 (0.46ms, 33.5MB)
테스트 4 〉	통과 (7.41ms, 36.2MB)
테스트 5 〉	통과 (15.19ms, 36.6MB)
테스트 6 〉	통과 (10.48ms, 36.4MB)
테스트 7 〉	통과 (0.63ms, 33.6MB)
테스트 8 〉	통과 (0.31ms, 33.4MB)
테스트 9 〉	통과 (4.39ms, 37.1MB)
테스트 10 〉	통과 (0.49ms, 33.5MB)
테스트 11 〉	통과 (0.21ms, 33.5MB)
테스트 12 〉	통과 (0.43ms, 33.6MB)
테스트 13 〉	통과 (0.95ms, 33.8MB)
테스트 14 〉	통과 (0.23ms, 33.5MB)

일부 케이스에서 10ms 이상인게 발견되어 조금 코드를 수정하였다.

 

const solution = (bridge_length, weight, truck_weights) => {
    let time = 0;
    let bridge = {
        container: [],
        weight: 0,
        limitWeight: weight,
        length: bridge_length
    };
    let waiting_truck = truck_weights.map(truck => { return {weight: truck, position: null} });
    
    while(true){        
        bridge.container.forEach(truck => truck.position += 1)
        
        if(bridge.container.length > 0 && bridge.length - 1 < bridge.container[0].position){
            bridge.weight -= bridge.container[0].weight;
            bridge.container.shift();
        }
        
        if(waiting_truck.length > 0){
            if(bridge.limitWeight >= (bridge.weight + waiting_truck[0].weight)){
                waiting_truck[0].position = 0;
                bridge.container.push(waiting_truck[0])
                bridge.weight += waiting_truck[0].weight;
                waiting_truck.shift();
            }else{
                const timeSkip = bridge.length - bridge.container[0].position - 1;
                bridge.container.forEach(truck => truck.position += timeSkip)
                time += timeSkip;
            }
        }else{
            if(bridge.container.length > 0){
                const timeSkip = bridge.length - bridge.container[0].position - 1;
                bridge.container.forEach(truck => truck.position += timeSkip)
                time += timeSkip;
            }
        }
        
        time ++;
        if(waiting_truck.length === 0 && bridge.container.length === 0) break;
    }
    
    return time;
}

테스트 1 〉	통과 (0.25ms, 33.4MB)
테스트 2 〉	통과 (0.25ms, 33.5MB)
테스트 3 〉	통과 (0.24ms, 33.5MB)
테스트 4 〉	통과 (1.51ms, 33.4MB)
테스트 5 〉	통과 (1.49ms, 35.7MB)
테스트 6 〉	통과 (1.86ms, 33.7MB)
테스트 7 〉	통과 (0.17ms, 33.4MB)
테스트 8 〉	통과 (0.26ms, 33.5MB)
테스트 9 〉	통과 (0.82ms, 33.6MB)
테스트 10 〉	통과 (0.30ms, 33.4MB)
테스트 11 〉	통과 (0.43ms, 33.4MB)
테스트 12 〉	통과 (0.35ms, 33.6MB)
테스트 13 〉	통과 (0.56ms, 33.4MB)
테스트 14 〉	통과 (0.21ms, 33.4MB)

뭔가 썩만족스럽진 않아서.. 추후에 좀더 효율적인 코드로 다시 도전해봐야겠다.

 

큐&스택 파트에서 큐(선입선출) 방식으로 풀어야하는 문제였다.

다리를 객체로 만들어 감당할 수 있는 무게와, 현재 다리에 올라가있는 트럭들,

그리고 현재 다리의 무게등을 정의한 채로 큐를 돌렸다.

 

쓸때 없이 시간이 흐르는 부분에서 시간을 뛰고 싶었는데

기다리는 트럭이 없는 상황에서도 작동하게 하고 싶었으나

조금.. 이래저래 꼬여서 일단은 넘어가기로 했다.

 

1. map()을 이용해 대기중인 트럭을 {weight: 트럭 무게, position: 다리에서의 트럭 위치}의 형태의 배열로 만든다.
2. bridge 객체를 선언한다. contaier : 현재 다리에 있는 트럭 객체를 담을 배열, weight : 현재 다리에 가해진 중량, limitWeight: 다리의 한계 중량, length: 다리의 길이
3. time 변수를 0으로 초기화 해둔다.
4. 반복문을 작성한다. 반복문은 내부에서 break 될때까지 무한 루프한다.
5. 반복문이 시작되면 현재 다리에 있는 트럭들을 이동시켜 줘야하므로 forEach()를 이용하여 bridge의 container에 담겨있는 트럭들의 position을 1씩 올려준다.
6. bridge의 container의 길이가 1이상이고 (차가 올라가 있고) bridge의 길이에서 - 1을 뺀 값보다 현재 bridge.container의 첫번째 원소의 position이 작다면, bridge.weight에서 해당 객체의 무게를 빼준 뒤, bridge.container의 첫번째 원소를 shift()를 이용하여 제거해준다. = 다리위에 차가 있고, 차가 다리를 지나간 경우 대응
7. 대기중인 트럭의 배열이 1 이상이고, 다리의 한계 중량이 현재 다리의 중량 + 대기중인 첫번째 트럭의 무게보다 같거나 크면 대기중인 트럭 배열의 첫번째 원소의 positoin 값을 null에서 0으로 바꿔주고, bridge.container에 넣어준다. 그 뒤, bridge.weight에 해당 객체의 무게를 더해주고, shift()로 대기중인 트럭 배열의 첫번째 원소를 제거해준다.
8. 위의 경우가 각각 아니라면, 다리의 길이에서 현재 다리에 올라가있는 첫번째 트럭의 position 만큼 뺀 값을 모든 트럭의 position에 더해주고, time 값도 그만큼 더해준다 ( 시간 스킵 )
9. 이후 시간을 1 더해주고, 대기중인 트럭의 배열이 비어있고, 다리 위의 컨테이너 배열이 비어있는 경우 반복문을 break 시킨다.