다리를 지나는 트럭

programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭

다리의 무게 제한과 트럭들이 지나는 걸 구현해주면 쉬운 문제이다.

문제의 조건에 트럭이 순서대로 가기 때문에, 대기 중인 트럭과 다리를 건너는 트럭을 표현하기 위한 자료구조로 큐를 사용했다.

현재 무게 제한을 저장해두고, 대기 중인 트럭에서 제한에 걸리지 않는다면, bridge 큐에 추가한다.

반대로, 대기 중인 트럭에서 제한에 걸린다면, 추가하지 않는다.

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
	//모든 트럭이 다리를 건너는 최소 시간
	int answer = 1;
	int limit = 0;
	//트럭의 무게 제한, 시간을 저장
	queue<pair<int, int>> wait, bridge;
	for (int i = 0; i < truck_weights.size(); i++)
		wait.push({ truck_weights[i], 0 });
	int w, t;
	//대기 중인 트럭이나 다리를 통과하는 트럭이 없을 때까지
	while (!wait.empty() || !bridge.empty()) {
		answer++;
		if (!wait.empty()) {
			w = wait.front().first;
			t = wait.front().second;
			if (limit + w <= weight) {
				wait.pop();
				limit += w;
				bridge.push({ w, t });
			}
		}
		int len = bridge.size();
		for (int i = 0; i < len; i++) {
			w = bridge.front().first;
			t = bridge.front().second;
			bridge.pop();
			if (t + 1 < bridge_length)
				bridge.push({ w, t + 1 });
			//다리에서 트럭 통과
			else
				limit -= w;
		}
	}
	return answer;
}