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

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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_lengthweighttruck_weightsreturn

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

class Q3Model{
        int location;
        int weight;

        public int getLocation() {
            return location;
        }

        public void setLocation(int location) {
            this.location = location;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }

//    https://programmers.co.kr/learn/courses/30/lessons/42583
//    다리를 지나는 트럭
    public int Question3(int bridge_length, int weight, int[] truck_weight) {
        int answer = 0;

        Queue<Q3Model> trucks = new LinkedList<>();
        Queue<Q3Model> bridge_trucks = new LinkedList<>();

        //parameter 초기화
        for (int i : truck_weight) {
            Q3Model model = new Q3Model();
            model.setLocation(0);
            model.setWeight(i);
            trucks.add(model);
        }

        // 다리에 있는 트럭 무게
        int bridge_weight = 0;

        while (!trucks.isEmpty() || !bridge_trucks.isEmpty()) {
            for (Q3Model model : bridge_trucks) {
                model.setLocation(model.getLocation() + 1);
            }

            // 다리에 트럭이 있는 경우
            if (!bridge_trucks.isEmpty()) {
                // 맨 앞 트럭의 위치가 다리 끝을 초과할 경우 빼준다.
                if (bridge_trucks.peek().getLocation() > bridge_length) {
                    Q3Model model = bridge_trucks.poll();
                    bridge_weight -= model.getWeight();
                }
            }

            if (!trucks.isEmpty()) {
                // 다리에 트럭이 들어갈수있는지 확인
                // 1. 무게 확인
                // 2. 다리에 있는 트럭 수 확인
                if (bridge_weight + trucks.peek().getWeight() <= weight
                        && bridge_trucks.size() < bridge_length) {
                    // 대기 -> 트럭으로보내기
                    Q3Model model = trucks.poll();
                    model.setLocation(1);
                    bridge_trucks.add(model);
                    // 다리에 있는 트럭 무게 추가
                    bridge_weight += model.getWeight();
                }
            }
            answer += 1;
        }

        return answer;
    }

※ 변수의 truck_weights를 truck_weight로 해놓고 풀었으니 복붙하시는분은 참고

이 문제는 문제 자체를 이해하는데에 많은 시간을 쏟았다.

문제 이해를 위해서는 아래의 조건이 전제된다.

1. 다리의 길이 (제한 트럭 갯수)만큼 트럭이 다리를 건너는데 시간이 든다.
   즉, 트럭은 한칸씩 이동하며 거리는 다리의 길이가 된다.
2. [대기 -> 다리] 와 [다리 -> 도착]이 한번에 이루어진다. 
   위 두가지 로직이 동시에 발생할 경우에 1초가 소요된다. 

사실 문제 자체는 그리 어려운 것 같지 않다. 다리로 들어오고 빠지는 방식이 Queue 자료형태와 완전히 동일하기 때문에 해당 자료형을 이용하여 쉽게 풀이할 수 있었다.