[Programmers] 스택/큐: Level 2 - 다리를 지나는 트럭 (javascript) 문제 풀이

문제

원본 사이트 : programmers.co.kr/learn/courses/30/lessons/42583

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

 

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 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

※ 공지 - 2020년 4월 06일 테스트케이스가 추가되었습니다.

 

풀이

문제 분석

• 정해진 순서에 따라 다리를 건너야함 → 순서를 신경쓸 필요는 없음
• 동시에 여러 대가 움직일 수 없으므로 한 대씩만 이동하면 됨

 

queue를 이용해 다리를 건너는 트럭을 확인 - (+8)

function solution(bridge_length, weight, truck_weights) {
    // answer: 모든 트럭이 다리를 건너는 데 걸리는 최소 시간(초)
    let answer = 0;
    // now_bridge: 현재 다리를 건너는 트럭들의 위치 상태
    let now_bridge = [];
    // now_weights: 현재 다리를 건너는 트럭들의 무게 합
    let now_weights = 0;
    // now_truck: 현재 다리에 올라설 트럭
    let now_truck = 0;
    // 0초일 경우의 모든 트럭들이 없는 상태로 초기화
    for(let i=0; i<bridge_length; i++){
        now_bridge.push(0);
    }
    
    // 다리를 건너고 있는 트럭의 무게 합(now_weights)이 0이 되면 모든 트럭이 이동한 경우이므로 반복문 종료
    do{
        // 1초++
        answer++;
        // 현재 무게에서 다리를 지나간 트럭의 무게를 뺌
        now_weights -= now_bridge.shift();
        // 다리에 올라설 트럭을 가져옴
        now_truck = truck_weights.shift();
        
        // (현재 무게 + 다리에 올라설 트럭의 무게)가 다리가 견딜 수 있는 무게(weight) 이하인 경우, 해당 다리를 이동시킴
        if(now_weights+now_truck <= weight){
            now_bridge.push(now_truck);
            now_weights += now_truck;
        }
        // (현재 무게 + 다리에 올라설 트럭의 무게)가 다리가 견딜 수 있는 무게(weight)를 초과하는 경우, 트럭을 다리에 올리지 않고 대기 상태로 되돌림
        else{
            now_bridge.push(0);
            truck_weights.unshift(now_truck);
        }
    }while(now_weights > 0);
        
    return answer;
}

• queue를 이용해 enqueue, dequeue 형식으로 트럭을 이동시킴
• 트럭이 오른쪽에서 출발해 왼쪽으로 이동한다고 가정
• 반대로 이동한다고 하면 pop과 unshift를 이용해 now_bridge를 만들면 될 듯
• 첫 번째 트럭이 다리에 올라선 순간부터 초를 재기 위해 do...while문 사용

 

결론

다른 사람의 풀이를 봤을 때, 이미 트럭이 다리가 견디는 무게만큼 찼는데 다리가 너무 길어 시간만 보내는 부분을 if문을 통해 한번에 해결해 퍼포먼스가 비약적으로 좋아졌다는 내용을 보고 퍼포먼스적으로 그런 부분들도 신경 써줘야한다는 것을 느낌