[프로그래머스 문제풀이] 10. 다리를 지나는 트럭

다리의 길이만큼 큐에 원소와 시간을 집어넣고 빼내오면 된다.

queue<pair<int, int>> bridge;

문제를 직관적으로 볼 때 큐에 원소와 다리길이 카운트를 쌍으로 집어넣으면 되겠다라고 생각할 수 있지만 다리길이 카운트 변수를 생성해서 계산하기 보다는 시간도 똑같이 카운트하니까 재활용하면 된다.

큐에 집어넣은 시간과 카운팅하는 시간이 다리 길이 만큼 차이날 때
다리에서 트럭을 빼내면 된다.

if (bridge.front().second + bridge_length == seconds)
{
	weight_in_bridge -= bridge.front().first;
	bridge.pop();
}

다리 앞에서 대기하고 있는 트럭이 없을 때 정답을 계산으로 구할 수 있다.
코드를 효율적으로 만들기 위해 위의 상황에서 다리를 건널 때까지 반복문을 돌리지 말고 조건문을 걸고 답을 계산하여 리턴하면 된다.

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
	int weight_in_bridge = 0;
	queue<pair<int, int>> bridge;
	int seconds = 0;

	for (size_t i = 0; ;)
	{
		if (weight >= weight_in_bridge + truck_weights[i])
		{
			bridge.push(make_pair(truck_weights[i], seconds));
			weight_in_bridge += truck_weights[i];
			++i;
		}

		if (i >= truck_weights.size())
		{
			return bridge_length + 1 + seconds;
		}
		else
		{
			++seconds;
			if (bridge.front().second + bridge_length == seconds)
			{
				weight_in_bridge -= bridge.front().first;
				bridge.pop();
			}
		}
	}
}

int main()
{
	cout << solution(2, 10, { 7,4,5,6 }) << endl;
}

실행결과

8

다리를 지나는 트럭 문제 링크