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

1.문제 링크

다리를 지나는 트럭

2. 풀이 전 계획과 생각

• 구현, 스택/큐 자료구조 이용

3. 풀이

#include <vector>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int second=0;
    int totalweight = 0;
    int index_truck = 0;
    vector<pair<int,int> > bridge; // second,weight

    while(true){
        second++;
        if(index_truck<truck_weights.size() && totalweight+truck_weights[index_truck]<=weight){
            totalweight += truck_weights[index_truck];
            bridge.push_back({bridge_length,truck_weights[index_truck]});
            index_truck++;
        }
        for(int i=0;i<bridge.size();i++){
            bridge[i].first-=1;
        }
        if(bridge[0].first==0) {
            totalweight -= bridge[0].second;
            bridge.erase(bridge.begin());
        }
        if(bridge.empty() && index_truck==truck_weights.size()) break;
    }

    return second+1;
}

totalweight 변수는 다리 위에 있는 트럭 무게 합으로 관리해줌.

index_truck은 몇번째 트럭까지 이동했는지를 알려줌.

bridege 벡터의 경우 {다리를 건너기까지 남은 시간, 트럭 무게} 저장.

while반복문에서 다리위에 트럭이 더 올라갈 수 있으면 bridge벡터에 추가시키고 반복문 한번 돌때마다 1초씩 증가한다.

bridge벡터가 비어있고 모든 트럭이 지나갔다면 반복문 종료.

4. 풀이하면서 고민했던 점

• 문제분류가 스택/큐로 분류되있었음 스택/큐 자료구조를 이용해 풀려고했지만 포기하고 vector를 이용함. 스택이나 큐의 경우 벡터와 다르게 모든 원소에 대한 접근이 불가능함.

5. 문제를 풀고 알게된 개념 및 소감

• 오래전에 못푼문제를 풀어서 기분이 좋음.