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

문제

프로그래머스

Pixabay 무료이미지

트럭 여러 대가 다리를 지나는데

트럭들은 길이가 1이라고 생각하고

다리의 길이는 bridge_length, 무게 제한은 weight인 조건에서

모두 지나가는데 걸리는 시간을 계산하는 문제이다.

 

나의 풀이 전략

1. while 문으로 시간을 계산한다.

2. 다리 위에 있는 트럭들을 큐(onBridge)로 구현한다.

3. 큐의 맨 앞 쪽 차량을 내보내면서 다음 차량이 들어올 수 있다면 다리 위에 올린다.

 

상세

0. answer 보단 time이 더 직관적이다.

truck_weights보단 Deque 형식의 waitings가 더 직관적이다.

그리고 다리 위의 트럭들을 구현하기 위해 onBridge라는 객체를 선언해주자.

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

    deque<int> waitings(truck_weights.begin(), truck_weights.end());
    deque<int> onBridge;

    return time;
}

(Deque가 기능도 많고 여러 함수들과도 잘 어울린다. 적극적으로 이용해야겠다.)

 

1. 우선 모든 트럭들은 다리를 지나갈 수 있다는 것을 알자. (제한 조건 참고)

따라서 while 문으로 대기 차량들이 다 빠져나갈 수 있을 때까지 시간을 재본다.

int solution(int bridge_length, int weight, vector<int> truck_weights)
{
    // ...

    while(waitings.size())
    {
        time++;
    }
    
    return time;
}

 

2. 다음 차량이 들어올 수 있으려면

우선 다리가 꽉 차 있으면 안 된다.

다리가 꽉 차면 맨 앞 차량을 빼주자.

int solution(int bridge_length, int weight, vector<int> truck_weights)
{
    // ...
    
    while(waitings.size())
    {
        // ...

        if(onBridge.size() == bridge_length)
            onBridge.pop_front();
    }
    
    return time; 
}

 

3. 다음으로 볼 것은 무게이다.

다리 위의 모든 차량의 무게(sumWeight)와 다음 차량의 무게(nextWeight)까지 합한 것이

다리의 무게제한(weight) 이하라면

다리 위에 차량을 올려주자.

int solution(int bridge_length, int weight, vector<int> truck_weights)
{
    // ...
    
    while(waitings.size())
    {
        // ...

        int sumWeight = accumulate(onBridge.begin(), onBridge.end(), 0);
        int nextWeight = waitings.front();

        if(sumWeight + nextWeight <= weight)
        {
            onBridge.push_back(waitings.front());
            waitings.pop_front();
        }
    }
    
    return time;
}

 

4. 만약 다음 차량을 무게제한 때문에 올리지 못한다면 어떻게 해야 하는가?

이대로 둔다면 while 문은 무한루프에 빠지게 될 것이다.

 

이를 방지하기 위해서는

무게가 0인 차량이 올라갔다고 생각하는 것이다.

int solution(int bridge_length, int weight, vector<int> truck_weights)
{
    // ...
    
    while(waitings.size())
    {
        // ...

        if(sumWeight + nextWeight <= weight)
        {
            onBridge.push_back(waitings.front());
            waitings.pop_front();
        }
        
        else onBridge.push_back(0);
    }
    
    return time;
}

 

5. 이렇게 하면 waitings는 다 비워졌다.

하지만 onBridge에 차량이 남아있다.

 

waitings가 다 비워진 시점은

waitings의 마지막 차량이 다리 위에 올라간 시점이다.

따라서 마지막 차량까지 건너는 시간(bridge_length)을 더해서 반환해줘야 한다.

int solution(int bridge_length, int weight, vector<int> truck_weights)
{
    while(waitings.size())
    {
        // ...
    }

    return time + bridge_length; // 주의!
}

 

전체 소스코드

#include <vector>
#include <queue>
#include <numeric> // accumulate
#include <iostream>
using namespace std;

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

    deque<int> waitings(truck_weights.begin(), truck_weights.end());
    deque<int> onBridge;

    while(waitings.size())
    {
        time++;

        if(onBridge.size() == bridge_length)
            onBridge.pop_front();

        int sumWeight = accumulate(onBridge.begin(), onBridge.end(), 0);
        int nextWeight = waitings.front();

        if(sumWeight + nextWeight <= weight)
        {
            onBridge.push_back(waitings.front());
            waitings.pop_front();
        }

        else onBridge.push_back(0);
    }

    return time + bridge_length;
}

int main()
{
    solution(2, 10, {7,4,5,6});
    return 0;
}