프로그래머스 - 다리를 지나는 트럭 - C++
문제 난이도
level 2
문제 설명
트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.
solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.
제한 조건
- bridge_length는 1 이상 10,000 이하입니다.
- weight는 1 이상 10,000 이하입니다.
- truck_weights의 길이는 1 이상 10,000 이하입니다.
- 모든 트럭의 무게는 1 이상 weight 이하입니다.
문제 풀이
다리 위에 올라가 있는 트럭을 큐를 이용하여 구현하였다. 변수들을 간단히 설명하자면,
- sum : 현재 다리 위의 트럭들의 무게의 합
- now : 현재 다리 위에 올라와 있는 트럭들
- length : 다리 위에 올라와 있는 트럭들의 남은 거리
트럭이 다리에 올라오면 sum에 무게를 더해주고 now와 length에 각각 트럭의 무게와 남은 거리를 추가해주고 answer에 1을 더해준다. 다리에 올라온 트럭들의 남은 거리를 1씩 줄이면서 만약 새로 올라올 트럭의 무게와 sum의 합이 weight를 넘지 않는다면 큐에 추가해주고 다시 answer에 1을 더해준다. 이 과정을 반복하다가 트럭이 모두 통과하게되면 반복을 멈추게 되고 이때의 answer가 최소 시간이 된다.
풀이 코드
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0, sum = 0;
queue<int> now, length;
while(1){
int size = length.size();
for(int i=0;i<size;++i){
int l = length.front();
length.pop();
if(l==1){
sum -= now.front();
now.pop();
continue;
}
length.push(l-1);
}
if(truck_weights.size()>0 && sum+truck_weights[0]<=weight){
sum += truck_weights[0];
now.push(truck_weights[0]);
length.push(bridge_length);
truck_weights.erase(truck_weights.begin());
}
++answer;
if(truck_weights.empty() && now.empty())
break;
}
return answer;
}