Programmers - 다리를 지나는 트럭

이준희·2022년 7월 8일

Algorithm

목록 보기
3/16

2개의 큐를 이용하여 비교적 쉽게 풀 수 있었던 문제였다.
트럭이 다리에 들어간 시간과, 다리 위에 있는 트럭을 저장하는 2개의 큐를 사용했다.

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int b_w = 0, index = 0, time = 1;
    queue<int> q;
    queue<int> s_time;
    q.push(truck_weights[index]); // 첫 번째 트럭을 다리 위에 올림과 동시에,
    b_w += truck_weights[index];  //  트럭이 들어간 시간을 큐에 넣어준다
    s_time.push(time);
    time++; index++;
    int temp_time, temp_weight;
    while(!q.empty()){			  // 다리에 트럭이 더이상 없으면 종료한다.
        temp_time = s_time.front();
        if(temp_time + bridge_length == time){	
        	// 맨 앞 트럭이 들어간 시간 + 다리의 길이를 한 시간이 현재 시간과 같으면,
            temp_weight = q.front(); 
            // 맨 앞의 트럭과 그 트럭이 들어간 시간을 큐에서 빼주었다.
            q.pop();
            s_time.pop();
            b_w -= temp_weight;		// 무게도 같이 빼주는 걸 잊지 말자!
        }
        if(b_w + truck_weights[index] <= weight){ 
        	// 다음 트럭과 현재 다리에 있는 트럭의 무게를 더했을 때 limit 무게를 넘지 않고, 
            if(index < truck_weights.size()){ // 더 들어갈 트럭이 있을 경우에, 
                q.push(truck_weights[index]); // 트럭과 트럭이 들어간 시간을 큐에 넣어준다
                b_w += truck_weights[index];
                s_time.push(time);
                index++;
            }
        }
        time++;
    }
    cout << time - 1;
    return time - 1;
}
profile
뉴비 개발자입니다!!

0개의 댓글