[프로그래머스 고득점 kit] 다리를 지나는 트럭 c++ (queue)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42583#

프로그래머스

 

문제 해설

이 문제의 경우, 먼저 들어간 트럭이 나가는 구조상 Queue가 적합하다. 하지만, '트럭이 진입하는 시점', '트럭이 나가는 시점' 을 잡는 것에서 헷갈릴 수 있는 포인트가 많다.

나는 기본적으로 만약 트럭이 바로 다리 위로 올라갈 수 있다면, 현재 시간 + 다리 길이로 해당 차가 나오는 시간을 구하고 Queue에 {무게,나가는 시간} 을 저장했다.

 

만약 현재 시간에 다음 트럭이 무게 제한에 걸려 다리에 들어갈 수 없다면, 해당 트럭이 다리에 올라갈 수 있을 떄까지 트럭을 Queue에서 내보내며 현재 진입하려는 트럭이 진입할 수 있는 시간을 구한다.

만약  트럭 Y가 트럭 X가 빠져나간 후에 다리에 진입 가능하다면, Y가 다리에 들어온 시간 == X가 다리에 빠져나가는 시간이된다.  이를 통해 문제를 해결하면 된다.

 

정답 코드

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    queue<pair<int,int>> qu; //현재 time에 트럭위에 있는 트럭들의 {무게, 진입시간} 순서쌍 저장
    queue<int> in;
    
    int w=0; //time의 시간에 다리위의 차량의 무게 합
    int time=0;
    for(int i=0;i<truck_weights.size();i++){
        int now=truck_weights[i];       
        while(!qu.empty()&& ( (w+now)>weight) ) {
                int f_w=qu.front().first, f_t=qu.front().second;
                qu.pop();
                w-=f_w;
                time=f_t+bridge_length;//진입한 차가 나간 시간.
        }
        qu.push({now,time});//내가 진입한 시간 저장. 
        w+=now;
        time++;//내가 진입하면서 든 시간 +1
        if(!qu.empty()&&time>=qu.front().second+bridge_length){//내가 진입하는 시간 동안 빠져나온 자동차가 있다면 제거해준다.
            w-=qu.front().first;
            qu.pop();
        }
    }
    answer=time+bridge_length;
    return answer;
}

 

주의
처음 구현에서 테스트  케이스 4,5,6,9 번이 실패하게 되었는데, 트럭이 진입하는 1초의 시간 사이에, Queue에 들어가있던 트럭이 빠져나오는 경우에도 time= 해당 트럭이 나오는 시간 으로 계산하기 떄문이다. 이 때문에, 현재 시간은 실제로 더 흘렀는데, 이전 트럭이 빠져나온 시간으로 시간이 치환되어 시간이 역행하는 문제점이 생긴다..

 

따라서 아래와 같이 내가 진입하는 사이에 빠져나온 트럭이 있다면 다리 위의 트럭을 저장해놓은 Queue에서 해당 트럭을 제거해준다. 

 time++;//내가 진입하면서 든 시간 +1
        if(!qu.empty()&&time>=qu.front().second+bridge_length){//내가 진입하는 시간 동안 빠져나온 자동차가 있다면 제거해준다.
            w-=qu.front().first;
            qu.pop();
        }