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

문제 : 다리를 지나는 트럭

 

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

 

 분석

고려할 조건들이 다소 복잡하다.

1. 대기차가 1대 이상 존재할 때, 차가 다리 위로 올라갈 수 있으면 진입시킨다.
2. 대기차가 있지만, 집입 불가 시 앞선 차량이 빠질 때까지 기다린다.
3. 다리 위 차량들은 시간이 흐를수록 거리가 줄어든다.
4. 대기차가 없고 다리 위 차가 있다면 시간은 계속 흐른다.
5. 대기차가 없고, 다리 위 차량도 없다면 종료.

 조건 1, 2 번 논리를 구현하기가 쉽지 않다. 쉽지 않은 이유는 습관 때문이다. 나도 그렇지만 사람 대부분은 아마 남은 길이를 처리할 때, 다리에 진입한 순서대로 처리하려고 할 것이다.

 하지만 깊게 생각해보면 굳이 남은 길이의 데이터들은 진입한 순서 정보까지 저장하고 있을 필요는 없다. 젤 짧은 길이가 결국 다리 위 진입한 차량들 중 가장 먼저 진입한 차량이기 때문이다.

 

다리 위에 있는 차량의 무게들은 진입한 순서대로 가져가되, 차량의 남은 길이는 순서 상관없이 다루면 다소 간결하게 답을 구할 수 있다.

 

 구현

int solution(int bridge_length, int weight, vector<int> truck_weights) {
	int answer = 0, current_weight = 0;
	queue<int> truck_weight_on_bridge, to_end_len;
	
	while (true)
	{
		int size = to_end_len.size();

		// 차량의 순서와는 독립
		// for문 내에서 1초가 흐른다.
		for (size_t i = 0; i < size; i++)
		{
			int len = to_end_len.front();
			to_end_len.pop();
			if (len <= 1)
			{
				current_weight -= truck_weight_on_bridge.front();
				truck_weight_on_bridge.pop();
				continue;
			}
			to_end_len.push(len - 1);
		}

		// 대기차량 진입 가능시 진입
		if (truck_weights.size() > 0 && current_weight + truck_weights.front() <= weight)
		{
			truck_weight_on_bridge.push(truck_weights.front());
			current_weight += truck_weights.front();
			to_end_len.push(bridge_length);
			truck_weights.erase(truck_weights.begin());
		}
		answer++;

		// base case
		if (truck_weights.size() == 0 && truck_weight_on_bridge.size() == 0) break;
	}
	

	return answer;
}