🎯문제
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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 |
✏️풀이
코드
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
int answer = 0;
// 큐 생성
Queue<Integer> bridge = new LinkedList<>();
// 다리의 길이가 1일 경우
if(bridge_length == 1) {
return truck_weights.length + 1;
}
// 트럭이 하나밖에 없는 경우
else if(truck_weights.length == 1) {
return bridge_length + 1;
}
// 다리의 개수만큼 큐 채워줌
for(int i = 0; i < bridge_length; i++) {
bridge.offer(0);
}
// 인덱스, 다리 위에 있는 트럭의 무게 총합
int index = 0, sumWeight = 0;
// 모든 트럭이 움직일 때까지
while(index < truck_weights.length) {
// 큐의 맨 앞의 값을 빼줌
sumWeight -= bridge.poll();
// 시간 증가
answer++;
// 현재 무게 총합과 들어올 트럭의 무게의 합이 허용범위라면
if(sumWeight + truck_weights[index] <= weight) {
// 해당 값을 넣고
bridge.offer(truck_weights[index]);
// 총합을 올려준 뒤 index 증가
sumWeight += truck_weights[index++];
}
// 허용범위가 아니라면 0을 넣어줌
else {
bridge.offer(0);
}
}
// 마지막 트럭의 값까지 넣어주기 위해 다리의 길이 더해줌
return answer + bridge_length;
}
}설명
큐를 사용해서 문제를 해결하였다.
그 전에 다리의 길이가 1일 경우에는 트럭이 하나밖에 지나갈 수 없으므로 지나가야하는 트럭의 개수 + 1을 반환해준다.
또한 트럭이 하나 밖에 없는 경우에도 여러 반복이 필요하지 않기 때문에 다리의 길이 + 1을 반환해준다.
이후 두 경우 어디에도 포함이 되지 않는다면 계산을 진행한다.
다리의 개수만큼 큐에 0의 값을 넣어준다. 이는 나중에 반복을 진행할 때 계산의 편의를 위해 넣어주는 것이다.
인덱스와 다리 위에 있는 트럭의 무게 총합을 저장할 변수를 각각 선언하고 while문을 진행한다. 이때 while문은 모든 트럭이 움직일 때까지 반복을 한다.
먼저 큐 앞에 있는 값을 빼준다. 그리고 시간을 증가시켜준다.
이후 새로운 트럭이 다리를 건널 수 있는지 판단한다. 현재 다리 위 트럭의 무게 총합과 새로 들어올 트럭의 무게의 합이 다리가 견딜 수 있는 무게라면 새 트럭의 무게를 큐에 넣고 총합에 더해준 뒤 인덱스를 증가시킨다.
만약 견디지 못하는 무게라면 0을 넣어준다.
예를 들어,
| bridge_length | weight | truck_weights | return |
|---|---|---|---|
| 2 | 10 | [7,4,5,6] | 8 |
일 때
큐는 [0, 0]의 값이 있을 것이다. 그리고 0을 빼준 뒤 7을 큐에 집어넣어준다.
그렇게 되면 큐는 [0, 7]이 된다.
반복문을 다시 진행하면서 0을 다시 빼주고 7이 앞으로 가게 되면서 [7]이 될 것이고, 이때 7+4가 weight보다 작거나 같은지 비교를 한다. 7+4 = 11이고 weight는 10이기 때문에 4는 큐에 들어올 수 없다. 따라서 큐에는 [7, 0]이라는 값이 채워지게 된다.
또 다시 반복문을 진행하면서 7이라는 값이 나오게 되고 [0, 4]가 들어간다. 이런 식으로 큐는 다리를 뜻하며 1초에 한칸씩 앞으로 진행하게 되는 것을 구현했다.
위의 반복을 모두 진행한 뒤에 나온 answer, 즉 반복 횟수와 함께 다리의 길이를 더해준 값을 반환해주면 문제를 해결할 수 있다!
💡느낀 점
처음 문제를 제대로 이해하지 못해서 아이디어를 생각하는데 오래 걸렸다. 아이디어를 생각하는 것보다 문제를 이해하는 게 더 오래 걸릴 줄은 몰랐다.. 문제를 이해하고 보니 하나씩 진행이 되는 과정을 표현하는 방법이 큐가 생각이 나서 큐를 가지고 문제를 해결할 수 있었다. 지금까지 여러 문제를 풀었지만 참 쉽게 넘어가는 문제들이 없구나라는 생각이 들었다. :)
링크
