[프로그래머스 Level 2] 다리를 지나는 트럭

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

 

 

풀이

• 다리에는 트럭이 최대 bridge_length 대 올라갈 수 있다.
• 다리는 weight 이하까지 무게를 견딜 수 있다.
• 모든 트럭이 움직일 때 1초의 시간이 흐른다.

 

다리에 올라간 트럭은 먼저 올라간 순서대로 내려와야 하므로 Queue 자료구조를 사용한다.

처음에는 대기 트럭도 Queue에 담아서 구현하려 하였지만 출력만 일어나기 때문에 굳이 그럴 필요가 없다는 사실을 깨달았다.

 

먼저 대기 중인 트럭을 다리에 올리는 작업이 필요했다.

단, 새 트럭을 올렸을 때 다리가 견딜 수 있는 무게를 초과한다면, 기존의 다리 위 트럭을 움직여서 새로운 트럭이 올라갈 수 있도록 해야한다.

그렇기 때문에 무작정 다음 트럭을 올리지 않고, while문의 무한 루프를 이용하여 대기 중인 트럭을 올릴 수 있는 상황이 되도록 연산하는 과정이 필요하다.

 

for (int t : truck_weights) {
    while (true){
        // t가 다리에 올라갈 수 있다면?
        // t가 다리에 올라갈 수 없다면?
    }
}

 

 

트럭을 다리에 올릴 때, 검사해야 하는 것은 길이와 무게 두 가지이다.

먼저 다리가 꽉 차 있는지 검사해야 한다. Queue의 size() 메서드를 사용해서 Queue에 입력된 트럭이 bridge_length와 같다면 트럭을 먼저 내보내야 한다.

그 다음 t의 무게를 더했을 때 weight를 초과하는지 검사해야 한다. 만약 weight를 초과한다면 0을 Queue에 추가하고 다리 위 트럭을 한 칸씩 전진시킨다.

 

if (bridge.size() == bridge_length){
    bridge_weight -= bridge.poll();

    if (bridge_weight + t <= weight){
        bridge.add(t);
        bridge_weight += t;
        sec++;
        break;
    } else {
        bridge.add(0);
        sec++;
    }
}

else {                    
    if (bridge_weight + t <= weight){
        bridge.add(t);
        bridge_weight += t;
        sec++;
        break;
    } else {
        bridge.add(0);
        sec++;
    }
}

 

반복문이 끝났다고 완전히 문제가 해결된 것은 아니다.

반복문이 끝난 시점은 대기 트럭이 다리 위로 올라간 시점이다. 문제는 트럭이 모두 다리를 건넌 경우에 대해 묻고 있으므로 마지막으로 다리 위에 올라간 트럭이 다리는 빠져나가는 시간인 bridge_length를 더해준다.

 

return sec + bridge_length;

 

 

전체 코드 (Java)

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int sec = 0;            // 시간
        int bridge_weight = 0;  // 다리의 현재 무게
        Queue<Integer> bridge = new LinkedList<>(); // 다리에 오른 트럭을 담는 큐

        for(int t : truck_weights){            
            while(true){
                // System.out.println(bridge);
                // 다리 위 트럭이 꽉 차 대기 트럭이 올라갈 수 없을 때
                if (bridge.size() == bridge_length){
                    bridge_weight -= bridge.poll();

                    if (bridge_weight + t <= weight){
                        bridge.add(t);
                        bridge_weight += t;
                        sec++;
                        break;
                    } else {
                        bridge.add(0);
                        sec++;
                    }
                }

                // 다리 위에 대기 트럭이 올라갈 수 있을 때
                else {                    
                    if (bridge_weight + t <= weight){
                        bridge.add(t);
                        bridge_weight += t;
                        sec++;
                        break;
                    } else {
                        bridge.add(0);
                        sec++;
                    }
                }
            }
        }

        return sec + bridge_length; // 마지막 트럭이 다리를 지나는데 걸리는 시간까지 합해준다.
    }
}

 

 

후기

대기 트럭을 다리 위로 올릴 때 필요한 조건을 생각하는 것이 중요한 문제였다. 문제의 조건을 차근차근 분석하는 것이 아직 부족하다고 느꼈다.