1. 문제에 대하여 📦

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42583

(1) 조건 분석 📊

대기 중인 트럭이 순서대로 다리를 지난다.
다리는 길이와 내구도 무게가 존재하는데, 최대 그 길이 수만큼의 트럭만 올라갈 수 있으며, 올라간 트럭의 무게 합이 다리의 내구도 무게를 넘어서면 안된다.
트럭은 1초에 다리를 한 칸씩 건넌다. 한칸 = 다리의 길이/1

2. 코드가 나오기까지 🛠️

KEY WORD: 큐 활용

모든 대기 트럭이 다리를 지날 때까지 반복해야한다.
반복의 기준은 초단위이다. 1초마다 버스가 움직이고, 새로운 버스가 다리에 들어오기 때문이다.

문제에 제시된 조건 그대로 구현하면 되는 것이라서, 추가 설명은 SUDO CODE에서 마저 하겠다.

(1) 시간복잡도 분석 ⏳

다리의 길이 10,000 , 트럭의 개수 10,000
모든 트럭이 다리의 길이만큼 이동하면 된다.

하나의 트럭당 10,000을 최종적으로 움직임으로,
최종적으로 $O( 10,000 \times 10,000) = 10^{8}$

이라서 시뮬레이션으로 구해도 시간 초과 없이 구할 수 있을 듯하다.

3. 코드 🌐

(1) SUDO CODE 💬

0. bridge 클래스 만들기
1. 대기 큐가 없으면서, bridge에 모든 트럭이 다리를 건널 때까지 다음을 반복한다.
    1. 한 번의 반복 당 1초 흐르기
    2. 다리의 끝에 온 트럭 이라면, 다리를 건너도록 하기
    3. 모든 다리 위의 트럭을 한 칸씩 앞으로 이동
    4. 대기 중인 트럭 중 최우선순위 트럭이 다리에 입장할 수 있는 지 체크
        1. 있으면 다리에 넣기
        2. 없으면 넣지 말고 다시 반복문 반복

(2) JAVA CODE ☕

import java.util.*;

class Solution {
    static class Bridge {
        int l;
        int w;
        int acc_cnt;
        int acc_w;
        int [] loc;

        public Bridge(int l, int w){
            this.l = l;
            this.w = w;
            this.acc_cnt = 0;
            this.acc_w = 0;
            this.loc = new int [l];
        }
    }

    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Bridge bridge = new Bridge(bridge_length, weight);
        ArrayDeque<Integer> bus = new ArrayDeque<>();

        for(int i = 0; i < truck_weights.length; i++){
            bus.add(truck_weights[i]);
        }
        int time = 0;
        while(!bus.isEmpty() || bridge.acc_cnt != 0){
            // 시간 흐르기
            time++;
            // 다리 건널 수 있는 버스 빼기
            if(bridge.loc[bridge.l-1] != 0) {
                bridge.acc_w -= bridge.loc[bridge.l-1];
                bridge.acc_cnt -= 1;
                bridge.loc[bridge.l-1] = 0;
            }
            // 다리 위 버스 한칸씩 진행
            int [] temp = new int [bridge.l];
            for(int i = 1; i < bridge.l; i++){
                temp[i] = bridge.loc[i-1];
            }
            bridge.loc = temp;
            // 다음 버스 넣을 수 있는지 확인
            if(!bus.isEmpty()){
                if(bus.peek() + bridge.acc_w > bridge.w || bridge.acc_cnt + 1 > bridge.l) continue;
                int now_weight = bus.poll();
                bridge.loc[0] = now_weight;
                bridge.acc_cnt ++;
                bridge.acc_w += now_weight;
            }
        }
        return time;
    }
}

4. 트러블 슈팅 or 배운 점📝

A. enhanced-Loop와 이터레이터 패턴

향상된 for문은 내부적으로 iterator로 변환이 되기 때문에 Collection을 상속받은 모든 자료 구조 클래스에서 사용이 가능하다고 하다.
따라서 enhanced-Loop를 사용하면 queue같은 자료구조도 안의 요소들을 하나씩 조회할 수 있다는 것이다.

이것을 몰라서, queue 대신 배열을 선택했는데, 다음엔 이를 활용해봐야 겠다.

B. Java의 Iterator 패턴

자바의 Iterator 객체는 Collections를 상속받은 모든 자료구조 클래스에서 활용될 수 있다. 이것은 java에서 iterator 패턴을 구현한 방법이다.

Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
queue.offer("C");

Iterator<String> iterator = queue.iterator();
while(iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
}