[Programers]다리를 지나는 트럭(Java Script)

출처 

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

---

❓Question

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.

※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

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

Example

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기트럭
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]	[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

---

❗Solution

function solution(bridge_length, weight, truck_weights) {
    //시간
    let time =0
    //다리에 있는 트럭무게, 나갈시간
    let qu = [[0,0]]
    //다리에 있는 트럭의 총 무게
    let weightBridge = 0;

    //대기 트럭과 다리를 건너는 트럭이 모두 없을 경우까지 반복
    while(qu.length > 0 || truck_weights.length > 0) {
        //현재시간이 제일 앞에 있는 트럭의 나갈 시간과 같다면 내보내고 다리위 트럭 무게 합에서 빼준다.
        if (qu[0][1] === time) weightBridge -= qu.shift()[0];

        if(weightBridge + truck_weights[0] <= weight) {
            //현재 다리에 있는 트럭 무게의 합 + 첫번째 대기 트럭의 무게가 총량보다 작거나 같으면 트럭 추가
            weightBridge += truck_weights[0];
            qu.push([truck_weights.shift(), time + bridge_length]);
        } else {
            //제일 앞트럭을 다리 끝으로 보낸다. 
            //시간 변경
            if (qu[0]) time = qu[0][1] -1
        }
        time ++;
    }
    return time
}

→ 반복문은 qu와 truck_weights가 둘다 빈배열이 될 때까지 반복한다.

→ time을 0부터 하면 qu에 초기값을 [0,0]으로 주어야 한다. (1로 주면 qu = [])

→ qu[0][1]이 트럭이 나갈 시간이므로 time과 같다면 qu에서 제거하고 weightBridge에서 나간 트럭의 무게를 빼준다.

→ 다리에 있는 트럭과 대기트럭[0]의 합이 총 무게보다 작다면 qu에 추가한다 [트럭무게, 시간 + 다리길이]

→ 작지않다면 앞트럭이 빠질때까지 트럭이 추가 될 일이 없으므로 시간을 qu[0][1] -1로 점프한다.(효율성 증가)

→ time += 1

Uploaded by Notion2Tistory v1.1.0