[C++][Programmers][스택/큐] 다리를 지나는 트럭

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

프로그래머스

---

*문제 설명

다리의 길이, 다리가 버틸 수 있는 무게의 최대 값, 무게를 담은 트럭 vector가 주어진다.

모든 트럭이 다리를 지날 때 몇초가 걸리는지를 반환하면 된다.

한번에 다리를 지나는 트럭 개수는 다리의 길이를 넘을 수 없고 다리가 버틸 수 있는 무게의 최대값을 넘길 수 없다.

트럭이 다리길이 1을 지날 때, 1초가 소요된다. 다리길이가 2라면 1초당 1씩 지나서 다 건너는데 총 3초의 시간이 필요하다.

 

*문제 해결법

건너야 하는 트럭의 리스트 크기만큼 queue를 생성하고 0으로 채워둔다.

queue에 현재 다리를 지나고 있는 트럭을 담는다.

다음 트럭의 무게가 동시에 건널  수 있는 트럭인지 체크한다.

무게의 합이 동시에 건널 수 없다면 0을 queue에 추가하고, 동시에 건널 수 있다면 다음 트럭을 queue에 넣는다.

 

*알아둘 것

걍 문제가 잘 이해가 안가서 한번 더 풀어보기를...

 

*코드

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0; //트럭이 지나가는데 걸린 시간
    int next_truck = 0; //다음에 이동할 트럭을 가리키는 인덱스
    int weight_sum = 0; //다리 위에 올릴 트럭들의 무게 합
    queue<int> on_bridge; //다리 위에 있는 트럭들의 리스트
    
    //맨 초기 다리를 다리길이 만큼 0으로 초기화
    for(int i = 0; i < bridge_length; i++){
        on_bridge.push(0);
    }    
    
    //다리 위가 비어있지 않을 동안 반복문 진행
    while(!on_bridge.empty()){
        //초 늘리기
        answer++;
        //다리 위 자동차 무게들의 합
        weight_sum -= on_bridge.front();
        //트럭 건너기 OK
        on_bridge.pop();
        
        if(next_truck < truck_weights.size()){
            //다리가 견딜 수 있는 무게를 넘지 않으면
            if(weight_sum + truck_weights[next_truck] <= weight){
                //무게 합에 다음 트럭 무게를 더함
                weight_sum += truck_weights[next_truck];
                //다리 위에 트럭을 올림
                on_bridge.push(truck_weights[next_truck]);
                //트럭 인덱스 하나 늘려주기
                next_truck++;
            }
            //다리가 견딜 수 있는 무게를 넘었다면 트럭 대신 0을 넣음
            else on_bridge.push(0);
        }
    }
    return answer;
}