[Programmers 문제풀이 JAVA] Level 2 다리를 지나는 트럭

 

📄 다리를 지나는 트럭

🔗 문제 풀러가기

Queue를 이용하여 문제를 해결하였습니다. 문제의 조건은 다음과 같습니다.

1. 트럭은 일차선 다리를 정해진 순으로 건넌다.
2. 트럭은 1초에 1만큼씩 이동한다.
3. 다리가 견딜 수 있는 무게가 정해져 있다.
4. 트럭이 다리에 완전히 오르지 않은 경우, 트럭의 무게는 고려하지 않는다.

먼저 정해진 순서대로 다리를 건너기 때문에 주어진 트럭들을 Queue에 넣습니다. 이때 각 트럭에 대한 상태(무게 및 이동 거리)를 관리하기 위하여 Truck이라는 클래스를 생성합니다. 그리고 현재 다리 위에 올라와 있는 트럭들을 관리하기 위하여 List을 생성합니다. 모든 트럭이 다리를 건너는 시간을 구하는 절차는 다음과 같습니다.

1. 대기중인 트럭들과 다리 위에 올라와 있는 트럭이 비어 있다면 모든 트럭이 건넜다는 의미이다.
2. 트럭은 정해진 순서대로 이동하기 때문에 다리 위에 올라가 있는 가장 첫 번째 트럭이 다리를 모두 건넜다면 다리 위에 올라와 있는 트럭 목록에서 제거한다. 이때 다리가 견딜 수 있는 무게를 제거 된 트럭 무게만큼 증가 시킨다.
3. 만약 대기중인 트럭이 다리위에 올라와도 다리가 견딜 수 있는 무게라면 대기중인 트럭 Queue에서 제거해 트럭을 다리 위에 올려 놓는다.
4. 다리에 올라와 있는 모든 트럭을 1만큼 이동 시킨다.

글보다는 코드로 보는게 더 쉽게 이해할 수 있습니다.

 

---

🌱 Truck의 정보를 나타내는 클래스

class Truck {
    int weight;
    int distance;

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

🌱 Solution 함수

public int solution(int bridge_length, int weight, int[] truck_weights) {
    int time = 0;
    Queue<Truck> waitTruckQueue = new LinkedList<>();
    List<Truck> TrucksOnBridge = new ArrayList<>();

    for (int trucks: truck_weights) {
        waitTruckQueue.add(new Truck(trucks, bridge_length));
    }

    while (!(waitTruckQueue.isEmpty() && TrucksOnBridge.isEmpty())) {
        time++;
        if (!TrucksOnBridge.isEmpty() && TrucksOnBridge.get(0).distance <= 0) {
            weight += TrucksOnBridge.get(0).weight;
            TrucksOnBridge.remove(0);
        }

        if (!waitTruckQueue.isEmpty() && weight - waitTruckQueue.peek().weight >= 0) {
            weight -= waitTruckQueue.peek().weight;
            TrucksOnBridge.add(waitTruckQueue.poll());
        }

        TrucksOnBridge.forEach(item -> item.distance--);
    }
    return time;
}

---

💡 Github에 더 많은 문제 풀이가 있습니다.

Programmers 문제 풀이

BaekJoon Online Judge 문제 풀이