문제
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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] | [] |
| 7 | [7,4,5,6] | [] | [] |
코드
function solution(bridge_length, weight, truck_weights) {
var answer = 0;
let pass = [] // 지나가고 있는 트럭
let timer = [] // 경과 시간 배열
let sum = 0 // sum을 통해서 다리 위의 최대 값을 확인
while ( truck_weights.length !==0 || pass.length !== 0){
if(timer[0] === bridge_length){
if(truck_weights.length !== 0){
sum = sum - pass.shift()
timer.shift()
}
else if(truck_weights.length === 0){
pass.shift()
timer.shift()
}
}
if (sum + truck_weights[0] <= weight ){
sum += truck_weights[0]
timer.push(0)
pass.push(truck_weights[0])
truck_weights.shift()
}
timer = Array.from( timer ,(v) => v+1)
answer += 1
}
return answer;
}-
반복문을 통해서 대기 트럭(truck_weights)이 0이 되면 끝나고, 지나가고 있는 트럭(pass)이 없으면 끝낸다.
||을 사용한 이유는, 처음 반복문에 진입 할 때는 대기 트럭이 꽉 차 있을 테고, 지나가고 있는 트럭이 하나도 없을 것이다. 그리고 반복문이 끝날 때에는 지나가고 있는 트럭, 대기 트럭 모두 비워져 있을 것이다. 즉,&&을 사용할 경우 처음 반복문이 진입 할 때 모든 트럭이 대기 트럭이기 때문에 반복문에 진입을 하지 못할 것이다. 그리하여||을 사용해서 반복문의 첫 진입을 할 수 있도록 해준다. -
첫 조건문에 경과 시간(
timer)가bridge_length와 같을 때 shift을 이용해 대기 트럭, 지나가고 있는 트럭을 제거해주고, 만일 대기 트럭이 있는 경우에는sum의 값을 빼주어, 다리를 통과한 트럭의 무게만 제거해주고, 만일 대기 트럭이 없는 경우 통과한 트럭과 트럭의 타이머만 빼준다.
(만일 대기 트럭이 없는데 `sum₩의 값을 빼주면 트럭이 진입하는 조건문에 걸리기 때문에 주의를 해준다.) -
다리 위에 있는 트럭들을
sum을 통해 무게를 전부 더해주고, 만일 다리 위에 더욱 올라갈 수 있는 상황이면,sum의 값에 그 다음 트럭 무게를 더하고, 타이머와 트럭을 지나가는 배열, 타이머 배열에 각각 넣어주고, 대기 트럭의 1번째 순서를 제거해준다.
timer = Array.from( timer ,(v) => v+1)는 timer에 각각 1씩 더해주는 역할을 한다.
from은 한 배열에 본인이 원하는 값을 초기화 혹은 각 요소에 map의 역할과 비슷한 역할을 해줄 수가 있다. Array.from()
스택이나 큐처럼 순서를 관리하는 문제들은 연습장에 그림을 그려가면서 하면 꼬이지 않고 보다 쉽게 풀어나갈 수가 있다.
