Problem 문제풀이
다리의 길이와 다리가 견딜 수 있는 무게가 있을 때 주어진 트럭들이 다리를 다 건너는데 걸리는 시간을 구하는
평범한 구현 문제이다. 처음에는 10000*10000이니까 시간복잡도가 아슬아슬 아닐까 싶었는데 다리가 견딜 수 있는
무게에 도달하면 제일 앞에 있는 트럭이 다리를 다 건널 때까지의 시간은 시뮬레이션을 하지 않고 SKIP해도 되기 때문에
시간 초과는 걱정하지 않아도 되었다.
-
다리 위에 트럭의 정보를 저장할
queue를 준비한다. -
다리 위에 트럭이 올라갈 수 없으면 제일 앞에 있는 트럭이 다리를 다 건널 때까지 시계를 매우 빠르게 돌린다.
-
다리 위에 트럭이 올라갈 수 있으면 트럭을 올리고 시간을 1 증가시킨다.
-
마지막 트럭까지 다리 위에 올라갔으면 그 시간 + 다리의 길이를
return한다.
1.
queue<pair<int,int>>on_bridge; //트럭이 다리에 올라간 시점, 해당 트럭의 무게
2.
if(on_bridge.front().first+bridge_length==answer) //트럭이 다리를 다 건넜을 경우 Queue에서 빼줘야 한다.
{
sum -= on_bridge.front().second;
on_bridge.pop();
}
if(sum+truck_weights[i]>weight) //트럭이 더이상 다리 위에 올라가지 못할 경우 시간여행을 한다.
{
pair<int,int> cross_bridge = on_bridge.front();
on_bridge.pop();
sum -= cross_bridge.second;
answer = bridge_length + cross_bridge.first;
i--;
}
3.
else
{
on_bridge.push({answer, truck_weights[i]});
sum += truck_weights[i];
answer++;
}
4.
while(on_bridge.size()>1)
{
on_bridge.pop();
}
answer = bridge_length + on_bridge.front().first;
return answer;
시간이 다 되었을 때 queue에서 트럭을 빼주는 작업을 하지 않아서 조금 헤맸던 문제였다.
그거 이외에는 실수할 부분은 없어보인다. 당신은 알고리즘 고수니까 >_<!!
전체 코드를 남기며 마무리한다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 1;
int sum = 0;
queue<pair<int,int>>on_bridge; //time, weight
for(int i=0;i<truck_weights.size();i++)
{
if(on_bridge.empty())
{
on_bridge.push({answer, truck_weights[i]});
sum += truck_weights[i];
answer++;
}
else
{
if(on_bridge.front().first+bridge_length==answer)
{
sum -= on_bridge.front().second;
on_bridge.pop();
}
if(sum+truck_weights[i]>weight)
{
pair<int,int> cross_bridge = on_bridge.front();
on_bridge.pop();
sum -= cross_bridge.second;
answer = bridge_length + cross_bridge.first;
i--;
}
else
{
on_bridge.push({answer, truck_weights[i]});
sum += truck_weights[i];
answer++;
}
}
}
while(on_bridge.size()>1)
{
on_bridge.pop();
}
answer = bridge_length + on_bridge.front().first;
return answer;
}