[프로그래머스] 다리를 지나는 트럭 (Lv.2)

---

문제 링크

---

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

문제 설명

---

길이 bridge_length, 최대 하중 weight인 다리가 있다. 트럭 무게 배열 truck_weights가 주어질 때, 모든 트럭이 다리를 건너는 최소 시간을 반환하라.

• 다리는 한 번에 bridge_length개의 트럭만 올라갈 수 있음
• 다리 위 트럭 무게 합이 weight를 초과하면 올라갈 수 없음
• 매 초마다 다리 위 트럭은 1칸 전진, 다리 끝에 도달하면 빠져나감

예) bridge_length=2, weight=10, truck_weights=[7,4,5,6] → 8

내 풀이

---

다리를 bridge_length 크기의 큐로 표현하고 초기값 0으로 채운다. 매 초마다 큐 앞에서 꺼내고(다리를 건넌 트럭), 뒤에 새 트럭 또는 0(빈 자리)을 넣는다. current_weight로 다리 위 총 무게를 추적하고, idx로 다음에 올릴 트럭을 추적한다. 모든 트럭을 다 올렸고 다리가 빌 때까지 반복한다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int time = 0;
    queue<int> bridge;
    for(int i = 0; i < bridge_length; i++) bridge.push(0);
    int current_weight = 0;
    int idx = 0;
    
    while(idx < truck_weights.size() || current_weight > 0)
    {
        time++;
        
        current_weight -= bridge.front();
        bridge.pop();
        
        if(idx < truck_weights.size() && current_weight + truck_weights[idx] <= weight)
        {
            bridge.push(truck_weights[idx]);
            current_weight += truck_weights[idx];
            idx++;
        }
        else
        {
            bridge.push(0);
        }
    }
    
    return time;
}

시간복잡도 분석

---

while 루프는 최악의 경우 모든 트럭이 한 대씩만 올라갈 수 있을 때 O(n × bridge_length).

n ≤ 10,000, bridge_length ≤ 10,000이므로 최악 O(10⁸) → 프로그래머스 기준 통과 가능하다.

오답노트

---

처음에 truck_on_bridge 카운터 방식으로 접근했는데, 각 트럭이 다리를 얼마나 건넜는지 추적할 수 없어서 로직이 틀렸다.

다리를 큐로 표현하는 발상으로 바꾼 후에도 두 가지 실수가 있었다.

1. 조건에서 bridge.front()를 새 트럭 무게로 착각 → truck_weights[idx]를 써야 함
2. bridge.back() == 0 조건을 불필요하게 추가 → 무게 조건만으로 충분

후기

---

진짜 많은 시행착오 끝에 문제의 해결법에 도달했다. 아무래도 조금 더 기초가 필요할 듯 하다.

• algorithm
• codingtest
• queue