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

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

프로그래머스

 

풀이

 

(차량의 무게, 차량이 다리를 다 건너는 시간)

을 쌍으로 가지는 큐 활용

 

truck_weights 벡터의 맨 처음 값과 그 트럭이 다리를 통과하는데 걸리는 시간(다리길이 +1) 를 먼저 큐에 삽입

>> 그래야 while 문 돌리기 가능하기 때문

 

이후 while문 반복을 통해

큐의 맨 앞과의 값을 비교하여 pop,

현재 도로 위의 차량들 무게와 다음 순서의 차량의 무게를 비교하여 push 수행

 

모든 차량이 지나가면 (q.empty() = true 라면) 반복문 탈출

time 값 리턴

 

int solution(int bridge_length, int weight, vector<int> truck_weights) {

	int sum = 0;	// 현재 다리 위의 무게
	queue<pair<int, int>> q;	// 현재 다리 위 차량 무게, 차량이 다리를 다 건너는 시간
	int idx = 0;	// 인덱스	
	int time = 1;	// 시간
	
	
	q.push(make_pair(truck_weights[idx], bridge_length+1));
	sum += truck_weights[idx++];

	while(!q.empty()){
    
		// 시간 증가
		time++;
		
		// (time == 맨 앞 차량이 통과하는데 걸리는 시간) 이라면
		// q.pop() 으로 도로에서 차량 빼고, sum 에서 해당 차량 무게 제외 
		if (time == q.front().second) {
			sum -= q.front().first;
			q.pop();	
		}

		// 다음 차량과 현재 도로위에 있는 차량의 무게를 더한 값 < 도로가 견딜수 있는 무게
		// 다음 차량이 도로에 들어갈 수 있다
		if (idx< truck_weights.size() && (sum+truck_weights[idx])<= weight) {
        
			// 큐에 차량의 무게, 다 지나가는데 걸리는 소요 시간을 pair로 삽입
			q.push(make_pair(truck_weights[idx], bridge_length+time));
            // 현재 도로위의 무게 증가, idx값 증가
			sum += truck_weights[idx++];
		}
	}
	return time;
}