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

• 출처: 프로그래머스 42583
• 분류: 스택/큐 · Lv.2

문제

일차선 다리에 최대 bridge_length대, 최대 weightkg까지 올라갈 수 있다. 트럭 무게 배열 truck_weights가 주어질 때, 모든 트럭이 다리를 건너는 최소 시간(초)을 반환하라. 트럭은 1초에 1칸 이동한다.

핵심

다리를 길이가 bridge_length인 큐로 모델링한다. 매초 큐를 한 칸씩 밀고, 다음 트럭이 올라갈 수 있으면 넣고 아니면 0을 넣는다.

풀이

#include <queue>
#include <vector>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    queue<int> bridge;
    for (int i = 0; i < bridge_length; i++)
        bridge.push(0);

    int time = 0;
    int onBridge = 0;
    int idx = 0;

    while (idx < truck_weights.size()) {
        time++;
        onBridge -= bridge.front();
        bridge.pop();

        if (onBridge + truck_weights[idx] <= weight) {
            bridge.push(truck_weights[idx]);
            onBridge += truck_weights[idx];
            idx++;
        } else {
            bridge.push(0);
        }
    }

    return time + bridge_length;
}

메모

• 다리를 0으로 채운 큐로 초기화하는 이유: 큐의 크기가 곧 다리 길이다. 매초 pop하고 push하면 트럭이 자동으로 1칸씩 전진하는 효과가 된다.
• onBridge: 현재 다리 위 트럭 무게 합. 매번 큐 전체를 순회하지 않고 누적값으로 관리한다.
• bridge.push(0): 트럭을 올리지 못하면 빈 칸을 넣는다. 큐 크기를 bridge_length로 유지하기 위함이다.
• return time + bridge_length: 마지막 트럭이 다리에 올라간 시점에 루프가 끝난다. 그 트럭이 다리를 완전히 건너려면 bridge_length초가 더 필요하다.

복잡도

시간	공간
O(N · L)	O(L)

N = 트럭 수, L = 다리 길이. 최악의 경우 트럭마다 L번 빈 칸을 넣으며 대기한다.