#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0, free_weight=weight;
queue<int> q;
queue<int> wait;
for(auto a : truck_weights) wait.push(a);
while(true)
{
if(wait.empty() && !q.empty()){
answer+=bridge_length;
break;
}
answer++;
if(q.size() == bridge_length){
free_weight += q.front();
q.pop();
}
if(q.size() < bridge_length && free_weight >= wait.front()){
q.push(wait.front());
free_weight -= wait.front();
wait.pop();
}else{
q.push(0);
}
}
return answer;
}
- key point!
1) queue가 가득찼을 때 pop()
과 push()
가 하나의 cycle에 존재해야 한다.
2) pop()
다음에 push()
를 해주는 순서가 중요!
3) queue의 size()
로 pop여부를 확인하기 때문에 빈 값(0)
을 넣어주어야 한다!
4) 마지막 모든 트럭이 queue에 올라갔을 때 bridge_length만큼 더하고 break!