[ JavaScript ] 프로그래머스 level2 42583번 다리를 지나는 트럭
다리를 지나는 트럭 #42583
프로그래머스 알고리즘 고득점 Kit > 스택/큐 > level2 다리를 지나는 트럭
문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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 |
처음에 문제가 이해가 가지 않아서 여러번 읽어보고, 출처도 읽어보았다.
프로그래머스 내의 설명이 조금 부족한 것 같기도 했다.
출처를 읽었을 떄 이해한 것은 bridge_length는 트럭 하나가 건너려면 걸리는 시간을 뜻하는 것 같았다.
첫번째 입출력 예를 그림/표로 그려본다면 아래와 같다.
나의 풀이
function solution(bridge_length, weight, truck_weights) {
let sec = 0; // 총 걸리는 시간
const size = truck_weights.length; // 전체 트럭의 수
const wait = truck_weights; // 대기 중인 트럭 배열
const bridge = []; // 다리 위인 트럭 배열 [weight,지나온 길이]
const finish = []; // 다리를 벗어난 트럭 배열
let weightOnBridge = 0; // 다리 위 트럭들의 무게 합
// 다리를 벗어난 트럭의 갯수가 총 트럭의 갯수보다 작을 때만 아래를 반복함
while (finish.length < size) {
// 다리의 가장 앞에 있는 트럭이 지나온 길이가 다리의 길이와 같으면 finish로 이동
if (bridge.length > 0 && bridge[0][1] == bridge_length) {
weightOnBridge -= bridge[0][0];
finish.push(bridge.shift());
}
// 다리 위 무게 + 들어갈 트럭의 무게가 한계값보다 작거나 같으면
// 다리에 트럭을 push하고, wait 배열에서 제거
if (weightOnBridge + wait[0] <= weight) {
bridge.push([wait[0], 0]);
weightOnBridge += wait[0];
wait.shift();
}
sec++; // 시간이 1초 증가되면
bridge.forEach((el) => el[1]++); // 다리 위 트럭들이 지나온 길이가 1 증가한다.
}
return sec;
}- 총 걸리는 시간 변수 sec
- 전체 트럭의 개수 size
- 대기 중인 트럭 배열 wait
- 다리 위인 트럭 배열 bridge
- bridge 배열의 값들은 [weight,지나온 길이] 형태로 push된다.
- 다리를 벗어난 트럭 배열 finish
- 다리 위 트럭들의 무게의 합 weightOnBridge
를 선언한다.
- 다리를 벗어난 트럭의 개수가 총 트럭의 수와 같으면 모든 트럭이 다리를 벗어난 상태이므로 그때까지 반복한다.
- 다리 위 트럭 중 가장 앞에 있는 트럭이 지나온 길이가 다리의 길이와 같으면 다 건넌 것이므로 finsish 배열로 이동한다.
- 다리 위 무게에 들어갈 트럭의 무게 값을 더한 것이 한계값을 넘지 않으면
bridge에 트럭을 넣고, wait에서 제거한다. - 시간을 1초 증가시키고,
- 다리 위 트럭들의 지나온 길이도 1씩 증가시킨다.
다른 풀이
function solution(bridge_length, weight, truck_weights) {
let sec = 0; // 걸리는 시간
let bridge = [[0, 0]]; // 다리 위 트럭 [무게, 빠져나가는 시간]
let weightOnBridge = 0; // 다리 위 총 무게
while (bridge.length > 0 || truck_weights.length > 0) {
// 다리의 첫 트럭의 빠져나가가는 시간이 현재 시간과 같으면 다리에서 제거
if (bridge[0][1] === sec) {
weightOnBridge -= bridge.shift()[0];
}
// 다리 위 무게 + 들어갈 트럭이 한계 무게를 넘지 않으면
// 다리에 트럭을 추가
if (weightOnBridge + truck_weights[0] <= weight) {
weightOnBridge += truck_weights[0];
bridge.push([truck_weights.shift(), sec + bridge_length]);
} else {
// 트럭을 더 넣을 수 없으면, 현재 시간을 다리의 첫 트럭이 빠져나가는 시간으로 jump
// 1을 빼주는 이유는, if문 밖에서 시간 증가가 이루어지기 때문
if (bridge[0]) sec = bridge[0][1] - 1;
}
sec++; // 시간 1초 증가
}
return sec;
}나의 풀이와의 차이점들은
- finish 배열 x
- bridge 배열의 값들의 두번째 값을 지난 다리의 길이가 아닌, 빠져나가는 시간으로 저장한 것
- 지나온 다리의 길이로 넣었을 때는 시간이 지날때마다 하나씩 증가시켜주었어야 했음
- 트럭을 더 넣을 수 없을 때 계속 시간을 1씩 증가시키면 루프를 돌지 않고, 현재 시간을 jump함
트럭의 수가 늘어날때마다 효율성의 차이가 크게 드러난다.
나의 풀이에서는 걸리는 초만큼 무조건 while을 돌게되는 반면에,
다른 풀이에서는 걸리는 시간을 jump했기 때문이다.
