[Programmers] level 2. 다리를 지나는 트럭(스택/큐) js
문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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 이하입니다.
| 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일 테스트케이스가 추가되었습니다.
풀이
function solution(bridLen, wei, truWei) {
let answer = 0;
let bridge = [];
let bridWei = 0;
for(let i = 0; i < bridLen; i++) {
bridge.push(0);
}
let goTruck = truWei.shift();
bridge.push(goTruck);
bridge.shift();
bridWei += goTruck;
answer++;
while(bridWei) {
bridWei -= bridge.shift();
goTruck = truWei.shift();
if(goTruck + bridWei <= wei) {
bridge.push(goTruck);
bridWei += goTruck;
} else {
bridge.push(0);
truWei.unshift(goTruck);
}
answer++;
}
return answer;
}풀이 설명
매개변수에는 bridLen(다리 길이), wei(다리가 버틸 수 있는 최대 무게), truWei(트럭들의 무게로 이루어진 배열)로 구성되어 있습니다.
변수로는 answer(걸린 시간), bridge(다리 길이로 만들어진 배열), bridWei(현재 다리 위에 있는 트럭의 총 무게)로 구성했습니다.
for(let i = 0; i < bridLen; i++) {
bridge.push(0);
}처음에 bridge를 다리 길이만큼 0으로 초기화를 시켜놓습니다. 예제 1번을 예시로 들면 bridge = [0,0];이 되겠죠.
아직 트럭이 출발하지 않을 때입니다.
트럭이 처음 출발했을 시에를 작성합니다.
let goTruck = truWei.shift();
bridge.push(goTruck);
bridge.shift();
bridWei += goTruck;
answer++;이 때 goTruck은 출발할 수 있는 트럭의 값입니다. 1번을 예시로 들면 goTruck = 7;
트럭이 출발했으니 다리에 있을 것이고 bridge.push(goTruck);에 해당되는 bridge의 값은 [0,0,7]이 됩니다.
다리 길이보다 1이 늘어났으므로 shift()를 통해서 앞에 0을 제거해줍니다. 그러면 [0,7]이 됩니다.
현재 다리 위에 있는 트럭의 무게가 늘어났으므로 bridWei 를 goTruck만큼 증가 시켜줍니다.
그리고 출발을 했으므로 answer에 1초를 증가시켜줍니다.
그럼 현재 변수들의 값들은 answer = 1; bridge = [0,7]; bridWei = 7;이 됩니다.
while(bridWei) {
bridWei -= bridge.shift();
goTruck = truWei.shift();
if(goTruck + bridWei <= wei) {
bridge.push(goTruck);
bridWei += goTruck;
} else {
bridge.push(0);
truWei.unshift(goTruck);
}
answer++;
}반복문을 통해서 총 걸린 시간을 구합니다.
변수들의 값에서부터 차근차근 가자면
bridWei 는 bridge 의 shift()한 값인 0을 빼줍니다. bridWei의 변동은 없지만 bridge는 shift()를 해줬기 때문에 [7]이 됩니다.
goTruck은 출발할 수 있는 트럭의 값이므로 대기중인 트럭들의 맨 앞의 숫자를 참조해줍니다. goTruck = 4;
이제 조건문을 통해서 다리가 지탱할 수 있는 무게보다 작거나 같으면 다리 위에 출발할 수 있는 트럭을 출발 시키고 아닐 시에는 0을 추가해주고 대기중인 트럭들의 배열에 출발할 수 있는 트럭의 값을 다시 넣어줍니다.
예시 1) while문 순서
1. 첫번째 싸이클
bridWei =7; goTruck =4;
wei 는 10이므로 else에 해당
bridge = [7] => bridge = [7,0]
truWei = [5,6] => truWei = [4,5,6]
answer = 2;
2. 두번째 싸이클
bridWei -= 7 해서 bridWei = 0; bridge = [0]; goTruck = 4; truWei = [5,6]
wei = 10 , if에 해당
bridge = [0,4] bridWei = 4;
answer = 3;
3. 세 번째 싸이클
bridWei -= 0 bridge = [4]; goTruck = 5; truWei = [6];
wei =10 , if에 해당
bridge = [4,5] bridWei = 9;
answer = 4
4. 네 번째 싸이클
bridWei = 5; bridge = [5]; goTruck = 6; truWei = [];
wei = 10 else 해당
bridge = [5,0]
truWei = [6]
answer = 5;
5.
bridWei = 0; bridge = [0]; goTruck = 6; truWei = []; wei = 10 if에 해당 / bridge = [0,6]; truWei = []; answer = 6;
6.
bridWei = 0; bridge = [6]; goTruck = x; truWei = []; if에 해당 / bridge = [6,0]; answer = 7;
7.
bridWei = -6; bridge = [0]; answer = 8; bridWei가 0보다 미만이게 되므로 반복문 종료