[프로그래머스]스택 큐 - 다리를 지나는 트럭

문제

 

풀이

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int count = 0; // 시간
    int noww = 0; // 현재 다리 위에있는 트럭들의 무게
    queue<pair<int,int>> q;
    
    for(int i=0 ;i<truck_weights.size(); i++){
        
        count++;
        
        if(q.front().second + bridge_length == count){
            noww-=q.front().first;
            q.pop();
        }
        
        while (noww + truck_weights[i] > weight){
            count = q.front().second + bridge_length;
            noww -= q.front().first;
            q.pop();
        }
        
        q.push(pair(truck_weights[i], count));
        noww += truck_weights[i];

    }
    
    count += bridge_length;
    
    return count;
}

pair 자료구조를 활용해 first엔 트럭의 무게 값을 , second엔 다를 건너기 시작한 시간 값을 주었다.

bridge_length는 트럭이 다리를 건너는데 걸리는 시간이다.

1. 현재 시간(count)이 다리를 건너기 시작한 시간(second) + 트럭이 다리를 건너는 데 걸리는 시간(bridge_length) 일 경우 pop 한다.
2. 다리에 있는 트럭의 무게(noww)가 다음 순서 트럭의 무게(truck_weights)를 견딜 수 없다면 pop 한다. 

 

 

---

 

다른 사람 풀이

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;

    int tot_w = 0;

    int t_front = 0;
    int t_cur = 0;

    int sec = 0;

    queue <int> q;

    while (t_front != truck_weights.size()) {
        if (!q.empty() && (sec - q.front() == bridge_length)) {
            tot_w -= truck_weights[t_front];
            ++t_front;
            q.pop();
        }
        if (t_cur != truck_weights.size() && tot_w + truck_weights[t_cur] <= weight) {
            tot_w += truck_weights[t_cur];
            ++t_cur;
            q.push(sec);
        }
        ++sec;
    }

    answer = sec;

    return answer;
}