다리를 지나는 트럭

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42583

❔ 문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다.
모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다.

트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

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

⚠️ 제한사항

• bridge_length는 1 이상 10,000 이하입니다.

• weight는 1 이상 10,000 이하입니다.

• truck_weights의 길이는 1 이상 10,000 이하입니다.

• 모든 트럭의 무게는 1 이상 weight 이하입니다.

---

💡 풀이 (언어 : Java & Python)

큐를 사용해서 푸는 것은 생각해냈지만, 각 트럭들의 시간초를 어떻게 카운트해주는지 방법이 떠오르지 않았다. 타인의 풀이를 참고했다. 각 케이스 별로 조건문으로 분기한다. 각 차의 시간초를 계산하는 것이 아니고 전체 시간을 따로 계산해준다. 새로운 차가 큐에 들어올때 시간을 +1해주고, 큐가 다 차면 앞의 차를 빼준다. 다리에 더 들어올 무게적 여유가 없으면 0인 트럭을 넣어주어 시간만 가게했다.

Java

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0, current_weight = 0;
        Queue<Integer> bridge = new LinkedList<>();
        for (int truck : truck_weights) {
            while (true) {
                // 다리에 트럭이 한대도 없으면 넣어주고 시간 +1, 무게 갱신
                if (bridge.isEmpty()) {
                    bridge.offer(truck);
                    answer++;
                    current_weight += truck;
                    break;
                // 다리가 꽉 찼으면 앞의 트럭을 빼주고, 무게 갱신
                } else if (bridge.size() == bridge_length) {
                    current_weight -= bridge.poll();
                // 다리에 다음 트럭이 들어올 여유가 있으면 추가하고, 시간 +1, 무게 갱신
                } else if (current_weight + truck <= weight) {
                    bridge.offer(truck);
                    answer++;
                    current_weight += truck;
                    break;
                // 다리에 무게 여유가 없으면 트럭이 안들어오고(무게 0), 시간 +1
                } else {
                    bridge.offer(0);
                    answer++;
                }
            }
        }
        return answer + bridge_length; // 마지막 트럭이 다리에 올라간 순간 for문 종료, 다 빠져나오는데 걸리는 시간(길이)
    }
}

Python

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    # 다리 위에 존재하는 트럭의 무게와 거리 정보
    on_bridge = [deque([]), deque([])] # 무게, 거리
    # truck_weights를 deque로 바꿔서 사용
    before_bridge = deque(truck_weights)

    # 대기트럭이 존재하지 않고 다리 위에도 트럭이 없을 때까지 반복
    while len(before_bridge) != 0 or len(on_bridge[0]) != 0:

        # 경과시간 1초씩 증가
        answer += 1

        # 맨 처음에 on_bridge[1][0]가 없어서 answer != 1해서 에러 안뜨게
        # 다리 위의 맨 앞의 트럭의 거리가 다리 길이와 같으면 그 트럭은 지금은 지난 트럭
        # 동시에 여러 트럭이 다리를 지날 일은 없어서 맨 앞에 트럭만 검사
        if answer != 1 and on_bridge[1][0] == bridge_length:
            on_bridge[0].popleft()
            on_bridge[1].popleft()

        # 무게가 여유있어 다리에 트럭을 추가하는 경우
        # 대기 트럭이 존재하고 다리 위 트럭들 무게 합 + 대기 트럭 무게 합이 
        # 다리 무게 제한보다 작을 때만 추가
        if len(before_bridge) != 0 and sum(on_bridge[0]) + before_bridge[0] <= weight:
            # 무게, 거리 = 0 입력
            on_bridge[0].append(before_bridge.popleft())
            on_bridge[1].append(0)

        # 매 턴마다 모든 트럭 거리 1씩 증가
        # 트럭들 거리 정보 리스트에 모든 원소 1씩 더해서 다시 저장
        on_bridge[1] = deque(map(lambda x: x+1, on_bridge[1]))

    return answer