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

다리 길이와 무게 제한이 있을 때, 트럭들이 순서대로 다리를 모두 건너는 최소 시간을 구하는 문제

 

1. 문제 유형

큐, 덱/데크 , 시뮬레이션, 구현

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 다리 길이만큼 배열을 만들고, 1초마다 배열 안의 값을 뒤로 한 칸씩 밀면서 트럭을 이동시키는 방식으로 생각했다. 그리고 배열 안의 값들의 합 + 새로 올릴 트럭 무게가 다리의 버틸 수 있는 무게 이하라면 트럭을 넣고, 아니면 못 넣게 하면 된다고 생각했다.

오답 원인: 아이디어 자체는 크게 틀리지 않았지만 매 초마다 배열 전체를 뒤로 미는 방식은 비효율적일 수 있다.
특히 다리 길이와 트럭 수가 최대 10,000까지 가능하므로 단순 배열 이동 방식은 시간복잡도 면에서 부담이 커질 수 있다.
또한 “다리 위 상태를 관리한다”는 생각까지는 갔지만 그걸 큐(Deque) 로 표현하면 더 자연스럽고 효율적이라는 점을 바로 떠올리지 못했다. 배열 길이를 설정하는것 처럼 큐에 미리 다리길이 만큼 0을 채워넣어서 다리를 만든다는 아이디어가 안떠올랐기 때문이다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 현재 다리 위 트럭들의 총 무게 + 다음 트럭 무게가 weight 이하여야 다음 트럭이 올라갈 수 있다. 또한 모든 트럭이 다리에 “올라간 시간”이 아니라, 완전히 빠져나간 시간까지 계산해야 한다.

 

풀이 아이디어:

1. 다리 위 상태를 Deque<Integer>로 관리하고, 큐의 크기를 항상 bridge_length로 유지한다.
   처음에는 다리가 비어 있으므로 0을 bridge_length만큼 넣어둔다.
2. 1초가 지날 때마다 맨 앞 값을 빼서 다리에서 빠져나간 것으로 처리하며, 빠진 값을 현재 다리 위 총 무게에서 빼준다.
3. 다음 트럭을 올릴 수 있으면 뒤에 해당 트럭 무게를 넣고 못 올리면 0을 넣어 빈 칸으로 시간을 흐르게 한다.
4. 모든 트럭을 다 올린 뒤에도 마지막 트럭이 다리를 완전히 건널 시간이 필요하므로 최종적으로 time + bridge_length를 반환한다.

4. 구현 코드

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Deque<Integer> bridge = new ArrayDeque<>();

        for (int i = 0; i < bridge_length; i++) {
            bridge.offerLast(0);
        }

        int time = 0;           
        int currentWeight = 0;  
        int truckIndex = 0;     

        while (truckIndex < truck_weights.length) {
            time++;

            currentWeight -= bridge.pollFirst();

            if (currentWeight + truck_weights[truckIndex] <= weight) {
                bridge.offerLast(truck_weights[truckIndex]);
                currentWeight += truck_weights[truckIndex]);
                truckIndex++;
            } else {
                bridge.offerLast(0);
            }
        }

        return time + bridge_length;
    }
}

시간 복잡도: O(N) / 공간 복잡도: O(N)

---

 

인사이트

• 처음에는 배열을 직접 뒤로 밀어야 한다고 생각했는데, 큐에서 앞에서 빼고 뒤에 넣는 것으로 표현할 수 있었다.
• 다리 위 무게 합도 매번 전체를 더하면 비효율적이므로 currentWeight 처럼 상태값으로 관리해야 한다.
• 일반 큐로도 풀 수 있지만 데크의 bridge.pollFirst();와 bridge.offerLast(0);가 트럭이 들어가고 나오는 방향이 직관적으로 보여서 사용했다. 둘의 성능 차이는 없다.

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/42583