[プログラマー]橋を渡るトラック
2883 ワード
これらの問題は、キューリソース構造について基本的な理解が必要です.
キューデータ構造?
あなたは銀行に税務を取りに来ました.待機票を引いて、先に来た人の仕事が終わるまで、画面に自分の番号が表示されるまで、仕事を処理することができます.君ほど遅れて来た人が先に呼び出されることはない.このような先入先出の方法を第1の先出と呼び,その代表はキューアルゴリズムである.
問題の解決順。
私は問題の順序を3つの段階に分けた.
1.トラックがあれば、トラックごとに1両ずつ車両を引く.
2.橋にトラックがなく、予備トラックがない場合は、進行時間に戻ります.
3.橋の上のすべてのトラックの重量+荷揚げされるトラックの最初の重量が橋の重量制限以下である場合、一番前の荷揚げされるトラックが橋に上がる.
この操作を繰り返すことで問題が解決しました.
問題解決コード
#include <string>
#include <vector>
using namespace std;
bool on_truck(vector<int> bridge)//트럭이 올라와있는지 검사
{
int i = 0;
while (i < bridge.size())
{
if (bridge[i] > 0)
return true;
i++;
}
return false;
}
void move_truck(vector<int>* bridge)//트럭을 한칸씩 땡기는 함수.
{
int i = 0;
while (i < bridge->size() - 1)
{
(*bridge)[i] = (*bridge)[i + 1];
i++;
}
(*bridge)[i] = 0;
}
int on_truck_weight(vector<int> bridge)//다리에 있는 모든 트럭의 무게를 리턴.
{
int i = 0;
int weight = 0;
while (i < bridge.size())
{
weight += bridge[i];
i++;
}
return weight;
}
int solution(int bridge_length, int weight, vector<int> trucks) {
int answer = 0;
int time = 0;
vector<int> bridge(bridge_length);
while (true)
{
if (on_truck(bridge))
move_truck(&bridge);
else if (trucks.size() < 1)
return time;
if (trucks.size() > 0 && (on_truck_weight(bridge) + trucks.front()) <= weight)
{
bridge.back() = trucks.front();
trucks.erase(trucks.begin());
}
time++;
}
return time;
}
Reference
この問題について([プログラマー]橋を渡るトラック), 我々は、より多くの情報をここで見つけました https://velog.io/@main_door/프로그래머스-다리를-지나는-트럭テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol