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

다리를 지나는 트럭(Level 2)

문제
전체 문제 보기

코딩테스트 연습 - 다리를 지나는 트럭

접근법

다리를 지나가는 트럭은 First-In First-Out(FIFO)의 성질을 지닌다. 항상 먼저 다리에 들어간 트럭이 먼저 빠져나온다. 그래서 다리를 하나의 Queue로 생각해볼 수 있다. Queue의 (FIFO)성질 만으로는 문제에서 언급한 다음의 조건을 만족시키기 부족하다.

• 트럭은 1초에 1만큼 움직인다.
• 다리는 무게 weight까지 견딘다.

우리는 다리를 하나의 Queue로 정의해서 사용하여 위의 조건을 충족시키기는 시뮬레이션을 만들기 위해서 다음과 같은 방법을 고민해볼 수 있다.

• 다리의 길이와 동일한 size를 가진 queue가 있다.
• queue의 원소로는 트럭의 무게 혹은 빈칸(0)이 들어갈 수 있다.
• 매 초마다 queue에서는 하나의 원소가 pop되고, 하나의 원소가 push된다.

이 조건들에 맞게 길이가 5인 다리를 초기화 하면 (time이 0인 상황) 다음과 같을 것이다.

그리고 1초일 때는 다음과 같이 무게가 7인 트럭이 queue에 들어올 수 있다.

다음 2초일 때는 4kg 트럭이 하중 초과로 들어올 수 없기 때문에 queue에 0을 push한다.

5초일 때의 상황은 다음과 같은 모습이 된다.

이렇게 queue에 0을 push한 덕분에 매 time마다의 다리의 상황을 queue에 시뮬레이션 해낼 수 있다. 이어서 계속 진행하면 다음과 같이 될 것이다.

다음으로 이 시뮬레이션의 종료 조건을 고민해야한다. 당연히 마지막 트럭이 무사히 다리를 지나면 시물레이션이 종료되는 것이 맞을 것이다. 하지만, queue에서 pop된 데이터 만으로는 이 트럭이 마지막 트럭인지 아닌지 알 방법이 없다. 또한 마지막 트럭이 다리에 올라갔다면, 그 트럭이 언제 다리를 지나게 될지는 자명한 사실이기에 굳이 시뮬레이션 할 필요가 없다. 우리는 마지막 트럭이 다리에 올라간 뒤에 다음과 같이 time에 다리의 길이를 더해주기만 하면 된다.

    // 마지막 트럭이 지나는데 필요한 시간을 더해준다.
    time += bridge_length;

구현

위의 설명들을 코드로 구현하면 다음과 같다.

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

using namespace std;

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

    queue<int> q;

    // 큐를 다리의 크기 만큼 0으로 채운다
    for(int i = 0; i < bridge_length; i++)
    {
        q.push(0);
    }

    // 마지막 트럭이 다리에 올라갈때 까지 시뮬레이션 반복
    while( index < truck_weights.size()) 
    {
        time++;

        // 다리를 지난 요소를 큐에서 제거
        total_weight -= q.front();
        q.pop();    

        // 다리에 트럭이 더 올라 갈 수 있다면 트럭을 push
        if(weight - total_weight >= truck_weights[index])
        {
            // next에 트럭의 무게 입력, 트럭 인덱스(index)++
            q.push(truck_weights[index]);
            total_weight += truck_weights[index];
            index++;
        }
        // 다리에 트럭이 더 올라 갈 수 없다면 0을 push
        else
        {
            q.push(0);
        }
    }

    // 마지막 트럭이 지나는데 필요한 시간을 더해준다.
    time += bridge_length;

    return time;
}