- 첫 풀이
처음에는 2차원 배열을 활용해 각 트럭이 통과한 시간을 별도로 저장해 모든 처리과정 후, 각 트럭이 다리를 건너는데 걸린 시간을 모두 더하는 방식으로 풀이하고자 하였다. 그러나 실패. 검색을 통해 대략적인 포인트를 확인하고 다시 풀어보았다.
- 정답 풀이
이 문제의 핵심은 다리의 길이라고 생각된다. 입력 예제 1번의 경우 다리의 길이는 2로 총 2대의 트럭이 다리에 올라갈 수 있는데, 이 과정에서 다리가 견딜 수 있는 하중을 고려해주는 것이 포인트 같다. 또한 애초에 문제에서 원하는 답이 모든 트럭이 다리를 지나는데 걸리는 최소 시간이므로, 다리가 견딜 수 있는 하중은 모든 트럭을 견딜 수 있게 주어진다.
고려해야 하는 경우의 수는 아래와 같다.
1. 첫 번째 트럭이 올라가는 경우 => 트럭은 무조건 올라갈 수 있다.
2. n 번째 트럭이 올라가는 경우 => n-1 번째 트럭의 무게 + n 번째 트럭의 무게 < 다리의 하중을 만족해야 함
=> n-1 번째 트럭의 무게 + n 번째 트럭의 무게 > 다리의 하중인 경우는 n-1 트럭 만 이동.
3. 다리의 길이 => 큐의 크기로 판단, 큐의 크기 == 다리의 길이가 되면, 가장 먼저 출발한 트럭이 다리의 끝에 도달.
(예제 1의 경우, 다리의 길이는 2이며 무게가 7인 첫 번째 트럭이 다리 끝에 도달하는데 2초가 걸림.)
이정도의 개념을 가지고 코드를 보면 이해하기 쉬울 것 같다.
import java.util.Queue;
import java.util.LinkedList;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
// 1. 마지막 트럭을 제외한 모든 트럭이 다리를 통과하는 데 걸린 시간.
int answer = 0;
// 2. 현재 다리의 트럭 무게 총합, 트럭들의 무게를 참조 할 변수.
int temp_weight = 0, idx=0;
// 3. 다리, 큐로 구현.
Queue<Integer> queue = new LinkedList<>();
// 4. 마지막 트럭을 제외한 모든 트럭을 통과시키기 위한 무한 반복.
while(true){
// 5. 마지막 트럭이 다리에 올라갔을 때, 벗어난다.
if(idx == truck_weights.length)break;
// 6. 다리에 있는 트럭이 끝에 도달하면, 도달한 트럭의 무게를 현재 다리의 트럭 무게 총합에서 빼준다.
if(queue.size() == bridge_length){
temp_weight-=queue.poll();
}
// 7. 현재 다리의 트럭 무게 총합 + 다리에 올라가야 하는 트럭의 무게 > 다리의 하중인 경우.
else if(temp_weight+truck_weights[idx]>weight){
// 7-1. 다리의 길이를 고려하기 위해 0인 값을 넣어 자리를 채우고, 1초 증가.
queue.offer(0);
answer++;
// 8. 위를 제외하고는 다리에 트럭이 올라간다.
}else{
queue.offer(truck_weights[idx]);
temp_weight+=truck_weights[idx];
answer++;
idx++;
}
}
// 9. 마지막 트럭이 다리에 올라간 상태에서 다리의 길이를 더해주면, 모든 트럭이 통과하는데 걸린 시간.
return answer + bridge_length;
}
}