[Programmers] Lv2. 다리를 지나는 트럭 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

큐(Queue)를 통해 다리 위에 있는 트럭들을 관리합니다. 트럭이 가지는 정보는 다리 진입 시각(enterTime)과 트럭 무게(weight)입니다.

struct Truck
{
	Truck(int enterTime, int weight) : _enterTime(enterTime), _weight(weight) { }
	int _enterTime;
	int _weight;
};

 

경과 시간(elapsedTime), 다리 위 트럭들의 총 무게 합(weightSum)도 같이 관리하며, 이제 본격적으로 트럭 관리에 들어갑니다.

int elapsedTime = 1;
int weightSum = 0;
queue<Truck> trucksOnBridge;

 

기본적인 알고리즘 흐름은 다음과 같습니다.

• 다리 위에 트럭이 없거나, 다리 위에 새로 트럭을 올릴 수 있다면, 새로운 트럭을 다리 위에 올립니다.
  • 이 때, 진입 시각을 저장해 놓습니다. 나중에 도착 시간 계산할 때 사용할 예정입니다.

 

 

경과 시간을 1초씩 증가시키면서 시뮬레이션을 돌리기에는 너무 비효율적이라고 생각했습니다. 트럭의 도착 시간을 계산할 수만 있다면, 1초씩 시뮬레이션을 돌려도 되지 않으니까요. 그래서 저는 트럭의 도착 시간을 계산하는 방식으로 접근하였습니다. 트럭의 도착 시간 공식은 다음과 같습니다.

"도착 시간" = "다리 진입 시각" + "다리의 길이"

 

이 계산을 위해 진입 시각을 적어 놓은 채, 다리에 진입시킨 것입니다. 다리에 추가로 트럭을 더 올릴 수 있다면, 계속 넣어주세요.

 

만약 더 올릴 수 없다면, 다리 위 맨 앞 트럭을 빼내어 도착 시간을 계산하여 그 시간으로 경과 시간을 초기화 시켜 주면 됩니다. 다만, 다리 길이가 너무 길어 계산한 도착 시간과 현재 경과 시간이 안 맞을 수 있으므로, 둘 중 큰 값으로 초기화 해줍니다.

 

다리 위 맨 앞 트럭을 빼낸 후에 바로 다음 트럭을 올리면 안 됩니다. 올릴 수 있는지 확인 후, 올릴 수 없다면 다시 맨 앞 트럭을 빼내어 계산 후 갱신하는 과정을 거쳐야 합니다.

 

계산 과정을 무사히 마쳤다면, 현재 트럭을 다리에 올리면 되겠지요.

모든 트럭을 다리에 올렸다면, 다리 위에 트럭이 없을 때까지 도착 시간을 계산하여 갱신해주면 됩니다.

 

✏️소스 코드 및 결과

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

struct Truck
{
	Truck(int enterTime, int weight) : _enterTime(enterTime), _weight(weight) { }
	int _enterTime;
	int _weight;
};

int solution(int bridge_length, int weight, vector<int> truck_weights) {
	int elapsedTime = 1;
	int weightSum = 0;
	queue<Truck> trucksOnBridge;

	for (int i = 0; i < truck_weights.size(); i++) {
		int truckWeight = truck_weights[i];

        // #1. 다리 위에 트럭이 없거나, 트럭을 더 올릴 수 있으면 올리기
		if ((trucksOnBridge.empty()) or (weightSum + truckWeight <= weight)) {
			trucksOnBridge.emplace(elapsedTime++, truckWeight);
			weightSum += truckWeight;
			continue;
		}

        // #2. 다리 위의 맨 앞 트럭을 빼내어 도착 시간 계산 후, 정보 갱신하기
		Truck frontTruck = trucksOnBridge.front();
		trucksOnBridge.pop();
		elapsedTime = max(frontTruck._enterTime + bridge_length, elapsedTime);
		weightSum -= frontTruck._weight;

        
        // #3. 다리에 다음 트럭을 실었을 때 최대 하중을 넘으면, 현재 루프를 다시 반복하여 #2번 로직 실행
		bool isOverWeight = weight < (weightSum + truckWeight);
		if (isOverWeight) {
			i -= 1;
			continue;
		}

        // #4. 다리 위 맨 앞 트럭을 도착 지점에 보냈다면, 새로 실을 트럭을 다리 위에 올리기
		trucksOnBridge.emplace(elapsedTime, truckWeight);
		weightSum += truckWeight;
		elapsedTime++;
	}

        // #5. 다리 위에 남아 있는 트럭들의 도착 시간 계산하기
	while (!trucksOnBridge.empty()) {
		Truck truck = trucksOnBridge.front();
		trucksOnBridge.pop();
		elapsedTime = truck._enterTime + bridge_length;
	}

	return elapsedTime;
}