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

문제 : programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭

풀이과정

트럭이 다리에 진입하려고 하는 경우, 두 가지 경우의 수가 존재한다.

1. 트럭이 다리에 진입할 수 있는 경우
2. 다리의 무게제한을 초과하기 떄문에 트럭이 다리에 진입할 수 없는 경우

 

1의 경우처럼 트럭이 다리에 진입하는데 아무런 문제가 없을 경우, 현재 다리 위에 있는 모든 트럭을 한칸씩 이동시킨 후 진입 대기중인 트럭을 다리에 진입시킨다. 이후 다음 트럭의 턴을 진행한다.

이 경우, 시간은 1초가 경과한다. 

 

2의 경우처럼 트럭이 다리에 진입하지 못하는 경우, 무게 제한에 걸리지 않을 때 까지 이미 다리 위에 올라간 트럭들 중 최소 1대 이상의 트럭이 빠져나와 주어야 한다.

이를 위해 현재 진입 대기중인 트럭이 진입에 성공할 때 까지 다음을 실행한다.

1. 다리의 맨 앞에 있는 트럭을 다리에서 빼낸다. 이 때 경과하는 시간은 트럭이 진입한 이후 경과한 시간과 다리의 길이에 따라 달라진다. 또한, 다리 위에 남아있는 다른 트럭들의 다리 진입 후 경과시간도 이 시간만큼 업데이트 해 준다.
2. 현재 진입 대기중인 아직도 다리에 진입할 수 없다면 다시 1로 돌아가서 이를 반복한다.
3. 현재 진입 대기중인 트럭이 다리에 진입할 수 있으면 그대로 다리에 진입시킨다. 시간은 경과하지 않는다. (맨 앞 트럭이 다리에서 빠져나오는 것과 대기중인 트럭이 다리에 진입하는 것은 동시에 이루어질 수 있기 때문)

 

마지막으로, 더이상 진입할 트럭이 없다면 총 경과시간을 바로 계산하여 반환한다. (총 경과시간 = 현재까지의 경과시간 + 마지막으로 진입한 트럭이 다리에서 빠져나오기 까지 남은 시간)

 

이를 flowchart로 나타내면 다음과 같다.

다리를 지나는 트럭 흐름도

 

소스코드

import java.util.ArrayDeque;

public class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Bridge bridge = new Bridge(weight);
        for (int truckWeight : truck_weights) {
            Truck truckIn = new Truck(truckWeight, bridge_length);
            bridge.accept(truckIn);
        }
        bridge.removeLastTruck();

        return bridge.getPassedTime();
    }
}

class Bridge {
    private final int weightLimit;

    private ArrayDeque<Truck> trucksOnBridge;
    private int currentWeight;
    private int passedTime;

    Bridge(int weightLimit) {
        this.weightLimit = weightLimit;
        this.trucksOnBridge = new ArrayDeque<>();
        this.currentWeight = 0;
        this.passedTime = 0;
    }

    public void accept(Truck truckIn) {
        // flag
        boolean waitSomeTrucksOut = false;
        // 새 트럭 진입 불가능. 현재 다리 위 트럭 중 1대 이상이 나가야 함.
        while (!this.isAcceptable(truckIn)) {
            waitSomeTrucksOut = true;
            // 맨 앞 트럭 out
            this.removeFirstTruck();
        }

        // 새 트럭 진입 가능
        if (!waitSomeTrucksOut) {
            // 다른 트럭이 나가길 기다렸다면 현재 트럭은 바로 들어갈 수 있지만
            // 그렇지 않다면 지금 있는 트럭들을 한칸씩 진행시킨 후 진입 시작
            this.passedTime++;
            for (Truck truck : this.trucksOnBridge) {
                truck.move(1);
            }
        }

        // 새 트럭 진입
        this.trucksOnBridge.offer(truckIn);
        this.currentWeight += truckIn.getWeight();

        // 한칸 이동한 트럭들 중 맨 앞 트럭이 다리에서 벗어났으면 제거
        if (this.trucksOnBridge.peek().getLeftTime() == 0) {
            this.removeFirstTruck();
        }
    }

    public void removeLastTruck() {
        // 더이상 진입할 트럭이 없으면 마지막 트럭이 빠져나가는 시간을 바로 계산
        this.passedTime += this.trucksOnBridge.getLast().getLeftTime();
        this.trucksOnBridge.clear();
    }

    private void removeFirstTruck() {
        Truck truckOut = this.trucksOnBridge.poll();
        int leftTime = truckOut.getLeftTime();
        this.currentWeight -= truckOut.getWeight();
        // 불필요한 반복은 하지 않도록 중단시킨다.
        if (leftTime == 0) {
            return;
        }
        this.passedTime += leftTime;
        // 맨 앞 트럭이 나가는 동안 경과한 시간 반영
        for (Truck truck : this.trucksOnBridge) {
            truck.move(leftTime);
        }
    }

    public int getPassedTime() {
        return this.passedTime;
    }

    private boolean isAcceptable(Truck truckIn) {
        if (this.currentWeight + truckIn.getWeight() <= this.weightLimit) {
            return true;
        }
        return false;
    }
}

class Truck {
    private final int weight;
    private int leftTime;

    Truck(int weight, int leftTime) {
        this.weight = weight;
        this.leftTime = leftTime;
    }

    public int getWeight() {
        return this.weight;
    }

    public int getLeftTime() {
        return this.leftTime;
    }

    public void move(int time) {
        this.leftTime -= time;
    }
}