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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42583?language=java

접근

큐(queue)를 활용하여 트럭이 다리에 올라설때마다 offer, 도착할때마다 poll 해주면 된다. 단, 여기서 다리에 올라설 수 있는 트럭의 무게 제한/개수 제한을 체크하면서 offer 해줘야 한다.

고민

다리에 올라간 트럭들의 위치를 알 수 있어야 한다. 그래야 해당 트럭들이 언제 도착하는지 알 수 있기 때문이다.

어떤 트럭이든지 다리에 올라갈 수 있다면 큐의 size를 체크해서 도착 처리하면 되기 때문에 상관 없지만, 무게 제한이 있기 때문에 다리 중간에 공백이 생기면 트럭들이 언제 도착할 지 알 수 없다.

-> 차량이 다리에 진입한 시간 정보를 저장함으로써 이 문제를 해결할 수 있다.

풀이

public class lv2_다리를지나는트럭_queue {
    //https://school.programmers.co.kr/learn/courses/30/lessons/42583?language=java

    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int curTime = 0;
        int curWeight = 0;
        int truckNum = 0;
        Queue<TruckInfo> q = new LinkedList<>();

        while (truckNum < truck_weights.length) {
            curTime++;

            //선두 트럭이 도착하는 경우
            // -> 현재 시간 - 트럭의 출발 시간 == bridge_length 이면 도착한것이다.
            if (!q.isEmpty()) {
                TruckInfo headTruck = q.peek();
                if (curTime - headTruck.enterTime == bridge_length) {
                    curWeight -= headTruck.weight;
                    q.poll();
                }
            }

            //트럭이 올라갈수 있으면 -> 올린다.
            if (q.size() + 1 <= bridge_length && curWeight + truck_weights[truckNum] <= weight) {
                q.offer(new TruckInfo(truck_weights[truckNum], curTime));
                curWeight += truck_weights[truckNum];
                truckNum++;
            }
        }

        //break 시점이 마지막 트럭이 다리에 오르는 시점이기 떄문에, 마지막 트럭이 도착하는 시간은 다리의 길이만큼 더 걸리기 때문에 마지막에 더해준다.
        return curTime + bridge_length;
    }

    static class TruckInfo {
        int weight;
        int enterTime;

        TruckInfo(int weight, int enterTime) {
            this.weight = weight;
            this.enterTime = enterTime;
        }
    }
}