Table of contents

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

1초에 1만큼 움직이면서 특정 무게를 갖는 트럭들과, 길이가 정해져있고 일정한 무게를 견딜 수 있는 일차선 다리가 주어졌을 때 모든 트럭이 다리를 건너기 위해 걸리는 시간을 초 단위로 구하는 문제이다.

@Test
public void testBridgeQueue() {
    Bridge bridge = new Bridge(2, 10);
    assertThat(bridge.crossOver(new int[]{7, 4, 5, 6})).isEqualTo(8);

    bridge = new Bridge(100, 100);
    assertThat(bridge.crossOver(new int[]{10, 10, 10, 10, 10, 10, 10, 10, 10, 10,})).isEqualTo(110);
    assertThat(bridge.crossOver(new int[]{10})).isEqualTo(101);
}

class Bridge {
    int length;
    int weight;

    Queue<Truck> waiting;
    Queue<Truck> onBridge;

    int space;

    public Bridge(int length, int weight) {
        this.length = length;
        this.weight = weight;
        space = weight;

        this.waiting = new LinkedList<>();
        this.onBridge = new LinkedList<>();
    }

    public int crossOver(int[] truckWeights) {
        for (int truckWeight : truckWeights) {
            waiting.add(new Truck(truckWeight, length));
        }

        int time = afterSecond(0);
        Truck first = waiting.poll();
        onBridge.add(first);
        space -= first.weight;

        while (!onBridge.isEmpty()) {
            time = afterSecond(time);

            if (onBridge.peek().isDone()) {
                space += onBridge.poll().weight;
            }

            if (!waiting.isEmpty()) {
                if (isCanCrossOver(waiting.peek())) {
                    Truck waitingTruck = waiting.poll();
                    onBridge.add(waitingTruck);
                    space -= waitingTruck.weight;
                }
            }
        }


        return time;
    }

    private boolean isCanCrossOver(Truck truck) {
        return space >= truck.weight;
    }

    private int afterSecond(int second) {
        for (Truck truckOnBridge : onBridge) {
            if (truckOnBridge.time > 0) truckOnBridge.time--;
        }
        return second + 1;
    }

    private class Truck {
        int weight;
        int time;
        public Truck(int weight, int time) {
            this.weight = weight;
            this.time = time;
        }
        public boolean isDone() {
            return this.time == 0;
        }
    }
}

길이와 무게를 가진 다리를 생성하고 crossOver로 트럭 배열을 전달한다. Bridge 클래스는 대기하고있는 트럭들과 다리에 있는 트럭들을 관리하기 위해서 큐를 사용한다. 다리의 길이는 트럭이 다리를 건너는데 소요되는 시간이며 반복문이 수행될 때마다 1초가 지난 것으로 간주한다. 모든 트럭의 무게는 다리의 무게 이하이므로, 첫번째 트럭은 1초가 되면 다리를 건너기 시작한다.

다리에 있는 모든 트럭들은 1초마다 time이 감소되어 0이 되면 다리 건너기를 완료한다. 첫번째로 대기하고있는 트럭은 다리가 자신의 무게를 버틸 수 있는 순간이 되면 다리를 건너기 시작한다.