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

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int currNum = 0, endNum = 0, sum = 0;
    vector<int> truck_times(truck_weights.size(), 0);	//다 지난 트럭 판별
    queue<int> q;	//현재 트럭
    q.push(truck_weights[currNum]);
    sum = q.front();	//무게합

    while (!q.empty())
    {
        int nextNum = currNum + 1;
        answer++;

        if (truck_times[endNum] == bridge_length)	
        //현재 맨앞 트럭이 다리를 지났나
        {
            sum -= q.front();
            q.pop();
            endNum++;
        }
        if (nextNum < truck_weights.size() && sum + truck_weights[nextNum] <= weight)
        //다음 트럭의 무게를 더한 sum이 다리 무게를 넘었나
        {
            sum += truck_weights[nextNum];
            currNum++;	//끝 트럭의 숫자
            q.push(truck_weights[nextNum]);
        }

        for (int i = endNum; i <= currNum; i++)	//첫 트럭에서 현재 트럭(끝 트럭)
        {
            if (truck_times[i] < bridge_length)	//아직 다리끝에 도달 못했을 때 time++
            {
                truck_times[i]++;
            }
        }
    }
    

    return answer;
}

 

풀이

1. 각 트럭의 시간과 각 트럭의 합, 끝 트럭과 맨 앞 트럭의 num을 가져온다.
2. queue를 사용하여 무게한도 내의 트럭들을 넣어준다. (단 한 경과시간에 하나만 넣을 수 있다.)
3. 판별 순서가 중요하다( 트럭이 지나갔나 -> sum보다 작으면 트럭추가 -> 다리 안 트럭들의 경과 시간 추가)
   현재 초는 queue가 비었을때 끝나므로 어디에 둬도 상관없음

 

확실히 생각하고 해야 문제를 빨리 풀 수가 있다.