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

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

문제 설명

트럭 여러대가 일차선 다리를 건널 때, 모든 트럭이 다리를 건너기 위해 최소 몇 초가 걸리는지 return 하기

제한사항

트럭은 1초에 1만큼 움직인다.
다리의 길이는 bridge_length이다.
다리는 최대 weight만큼의 무게를 견딜 수 있다.
트럭은 대기하고 있는 순서대로 다리를 건넌다.

문제풀이

1. 트럭을 다리에 올릴 수 있는지 확인한다.
2. 트럭에 다리를 올릴 수 있을 때
   다리에 올라간 트럭 큐에 push 하고, 다리 위 트럭의 무게에 트럭의 무게를 추가한다.
3. 트럭에 다리를 올릴 수 없을 때
   다리가 채워지지 않았을 때 : 다리에 올라간 트럭 큐에 0을 추가한다.
   다리가 꽉 찼을 때 : 다리에 올라간 트럭 큐의 맨 앞 트럭을 pop 한다.

코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int idx = 0;
    
    queue<int> on_bridge;
    int on_bridge_weight = 0;
    
    while(1){
        if(idx == truck_weights.size()) break;
        
        int current_truck_weight = truck_weights[idx];
        answer ++;

        if(on_bridge.size() == bridge_length){
            on_bridge_weight -= on_bridge.front();
            on_bridge.pop();
        }
        
        if(on_bridge_weight + current_truck_weight <= weight){
            on_bridge.push(current_truck_weight);
            on_bridge_weight += current_truck_weight;
            idx ++;
        }
        else{
            on_bridge.push(0);
        }
    }
    
    answer += bridge_length;
    return answer;
}

맨 마지막 트럭이 다리 위로 올라가면 while문이 종료된다.
마지막 트럭이 다리 위로 올라간 다음, 다리를 빠져나올 때까지 bridge_length만큼 시간이 소요되므로 맨 마지막 트럭이 다리 위로 올라갈 때 까지 걸린 시간 + bridge_length가 답이 된다.

시간 복잡도

O(N)
N : answer - bridge_length

문제 풀 때 참고 사이트