Programmers - 스택/큐 [다리를 지나는 트럭]

1. 문제

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

 

경과 시간                          다리를 지난 트럭                다리를 건너는 트럭              대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

bridge_length                     weight                             truck_weights                     return

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

2. 내풀이

import java.util.*;

// 트럭이라는 클래스를 만든다.
class Truck {
    // 다리를 처음 들어갔을때 시간을 저장한다.
    private int passingTime = 0;
    // 트럭의 무게를 저장한다.
    private int weight = 0;

    public int getPassingTime() {
        return passingTime;
    }

    public int getWeight() {
        return weight;
    }

    public void setPassingTime(int passingTime) {
        this.passingTime = passingTime;
    }

    // 트럭을 생성할 때 트럭의 무게를 집어넣어준다.
    public Truck(int weight) {
        this.weight = weight;
    }
}

class PassingTruck {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        // 다리는 Queue 형태이므로 queue로 구현한다.
        // ArrayList로 비슷하게 할 수 있으나 index값으로 삭제하고 불러오는데 매우 에러가 많다.
        Queue<Truck> waitingTrucks = new LinkedList<>();
        Queue<Truck> passedBridge = new LinkedList<>();
        Queue<Truck> inBridge = new LinkedList<>();

        // 트럭들을 waitingTruck에 옮겨 닮는다.
        for (int truckWeight : truck_weights) {
            waitingTrucks.add(new Truck(truckWeight));
        }
        // 시간은 0부터 시작한다.
        int time = 0;
        // 트럭들이 모두 다리를 지나가면 멈춘다.
        while (!(passedBridge.size() == truck_weights.length)) {
            // 트럭이 다리를 지나간 것을 먼저 체크해야 다리 위에 있는 것들이 clear된다.
            // 다리에 있던 마지막 트럭이 다리를 건넌다
            // 다리에 트럭이 있다면 실행
            if (!inBridge.isEmpty()) {
                // 다리에 있는 마지막 트럭이 다리에 있던시간(현재 시간 - 들어올 때 시간)이 다리길이와 같거나 크다면 다리를 지나감
                if (time - inBridge.peek().getPassingTime() >= bridge_length) {
                    passedBridge.add(inBridge.peek());
                    inBridge.poll();
                }
            }

            // 다리에 있는 모든 트럭의 무게를 더한다.
            int sum = 0;
            if (!inBridge.isEmpty()) {
                for (Truck truck : inBridge) {
                    sum += truck.getWeight();
                }
            }

            // 현재 다리위의 무게와 들어올 차량의 무게를 더한것이 다리한계보다 낮다면 다리에 올린다.
            // 기다리는 트럭들이 없을시 실행
            if (!waitingTrucks.isEmpty()) {
                if (sum + waitingTrucks.peek().getWeight() <= weight) {
                    waitingTrucks.peek().setPassingTime(time);
                    // 다리위에 올린다.
                    inBridge.add(waitingTrucks.peek());
                    waitingTrucks.poll();
                }
            }
            // 다음시간.
            time++;
        }
        return time;
    }

    public static void main(String[] args) {
        PassingTruck passingTruck = new PassingTruck();
        int bridge_length = 2;
        int weight = 10;
        int[] truckWeight = {7, 4, 5, 6};
        System.out.println(passingTruck.solution(bridge_length, weight, truckWeight));
    }
}

- 다리를 지난 트럭이 있는지 없는지 확인하는 것부터 시작해야한다. 그래야 다리를 건너는 트럭의 Queue가 해결된다.

 

- 다리를 건너는 트럭의 조건은 현재 시간 - 트럭이 다리에 들어온시간 >= 다리길이 이다.

 

- ArrayList를 쓰면 Exception in thread "main" java.util.ConcurrentModificationException 이 에러가 무진장 생긴다.

루프를 돌면서 인덱스를 삭제하면 size()계산이 안되어 현 index 파악에 문제가 생긴다.

그러지 않기 위해서 루프를 최대한 쓰지 않고 Queue로 문제를 해결한다. peek()과 poll()은 그러한 문제가 없이

해당 인덱스를 삭제하거나 반환한다.
출처: https://offbyone.tistory.com/170 [쉬고 싶은 개발자]불러오는 중입니다...

루프 도중 안전하게 삭제하기

 

- 인덱스 범위 에러또한 뜨는데 이것은 반드시 사용하고자 하는 Queue가 비었나 비어있지 않나 체크하고 

실행한다.

 

- 참고로 타입을 알아낼 때에는 Object.getClass().getName()를 하면 타입이 나온다.

3. 다른사람풀이

import java.util.*;

class Solution {
    class Truck {
        int weight;
        int move;

        public Truck(int weight) {
            this.weight = weight;
            this.move = 1;
        }

        public void moving() {
            move++;
        }
    }

    public int solution(int bridgeLength, int weight, int[] truckWeights) {
        Queue<Truck> waitQ = new LinkedList<>();
        Queue<Truck> moveQ = new LinkedList<>();

        for (int t : truckWeights) {
            waitQ.offer(new Truck(t));
        }

        int answer = 0;
        int curWeight = 0;

        while (!waitQ.isEmpty() || !moveQ.isEmpty()) {
            answer++;

            if (moveQ.isEmpty()) {
                Truck t = waitQ.poll();
                curWeight += t.weight;
                moveQ.offer(t);
                continue;
            }

            for (Truck t : moveQ) {
                t.moving();
            }

            if (moveQ.peek().move > bridgeLength) {
                Truck t = moveQ.poll();
                curWeight -= t.weight;
            }

            if (!waitQ.isEmpty() && curWeight + waitQ.peek().weight <= weight) {
                Truck t = waitQ.poll();
                curWeight += t.weight;
                moveQ.offer(t);
            }
        }

        return answer;
    }
}

- 내풀이와 비슷하지만 훨씬 간결하다. 대기트럭 Queue를 만들지 않고 현재무게를 매번 계산하지 않았따.

- 다리위에 현재 위치를 나타내는 move라는 변수를 사용함으로서 다리를 통과하는 시점을 계산했다.

4. Tip

- ArrayList대신 Queue와 Stack이 왜 있는지 고려해보자. 

- Queue는 LinkedList로서 LinkedList의 특징을 생각하자.