[프로그래머스,Level 2] 다리를 지나는 트럭 (JAVA 구현)

- 첫 풀이

  처음에는 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;
    }
}