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

Pixabay로부터 입수된 Alexa님의 이미지 입니다.

---

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

프로그래머스

 이 문제는 다리의 길이, 다리가 견딜 수 있는 무게, 트럭 별 무게가 주어질 때, 모든 트럭이 다리를 건너기 위해 필요한 최소 시간을 구하는 문제이다. 이 문제를 풀기 위한 흐름은 문제 설명을 보면 이해하기 쉽다. 문제 설명에도 나와있듯, 각 시간마다 트럭이 다리를 벗어날 수 있는지, 트럭이 다리에 올라갈 수 있는지만 검사하면 된다. 만약 현재 시간에서 다리 제일 앞에 있는 트럭이 다리를 벗어날 수 있다면, 그 트럭을 다리 위에서 제거하면 된다. 그 후, 현재 대기 중인 트럭이 다리 위에 올라갈 수 있으면 다르에 현재 트럭을 올린다.

 이를 구현하기 위해 고민해야할 것이 두 가지가 있다. 우선, 먼저 다리에 올라간 트럭이 먼저 다리를 나가는 것을 어떻게 구현하냐는 것이다. 이는 큐(Queue)를 이용해 구현할 수 있다. 큐는 간단히 말해 먼저 들어간 것이 먼저 나오는 구조로, 먼저 줄을 선 사람이 먼저 들어가는(나가는) 것을 생각하면 된다. 문제의 상황도 이와 같기에 큐를 이용할 것이다. 그리고 트럭이 다리를 나갈 수 있는지 판별할 조건이다. 이는 트럭이 다리에 올라간 시간을 이용해 판별할 수 있다. 예를 들어, 문제 설명의 예시에서 무게가 4인 트럭은 시간이 3일 때 다리에 올라갔다가 시간이 5일 때 다리를 벗어났다. 이는 시간이 3일 때 다리에 올라가 다리 길이 2만큼의 시간이 지난 후에 다리를 벗어난 것이므로, 현재 시간 - 다리에 올라간 시간과 다리 길이를 비교하여 다리를 벗어날 수 있는지 아닌지를 판별할 수 있다. 이것들을 고려한 흐름은 다음과 같다.

1. 반복문을 이용하여 2번부터의 과정을 실시한다.
2. 만약 다리 위에 트럭이 존재한다면, 그 트럭이 다리를 나갈 수 있는지 검사한다.
   • 만약 현재 시간에서 현재 다리의 가장 앞에 있는 트럭의 다리 위에 올라온 시간을 뺀 값이 다리 길이와 같거나 크다면, 그 트럭은 다리를 나갈 수 있다.
3. 만약 트럭이 다리 위에 올라갈 수 있다면, 다리 위에 넣는다.
   • 만약 다리 위의 트럭 수가 다리 길이보다 작고, 현재 다리 위의 총 트럭 무게 + 현재 트럭 무게가 주어진 무게 제한보다 작을 경우, 다리 위에 올라갈 수 있다.

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    
    int truckIdx = 0;       // 트럭의 인덱스
    int current = 1;        // 현재 시간 (경과 시간 1부터 트럭이 다리에 올라갈 수 있다.)
    int totalWeight = 0;    // 다리 위의 트럭들 무게의 합
    queue<pair<int, int>> trucksOnBridge; // first: 무게, second: 다리에 올라온 시간
    
    // 모든 트럭이 다리에 올라가지 못했거나, 다리 위에 트럭이 존재하는 경우 반복문을 진행한다.
    while(truckIdx < truck_weights.size() || trucksOnBridge.size() > 0)
    {   
        // 이미 다리를 건넌 트럭은 다리 위에서 제거한다.
        while(trucksOnBridge.empty() == false)
        {
            pair<int, int> truck = trucksOnBridge.front();
            
            // 현재 시간 - 트럭이 다리에 올라간 시간 >= 다리 길이 -> 다리를 건넘
            if (current - truck.second >= bridge_length)
            {
                trucksOnBridge.pop();
                totalWeight -= truck.first;
            }
            else
                break;
        }
        
        // 만약 현재 트럭의 인덱스가 주어진 트럭의 범위 안이라면
        // 트럭이 다리에 올라갈 수 있는지 검사한다.
        if (truckIdx < truck_weights.size())
        {
            int currentTruck = truck_weights[truckIdx];
            
            // 만약 다리에 트럭이 올라갈 공간이 있으면서
            // 현재 다리 위의 트럭들의 총 무게 + 현재 트럭 무게 <= 주어진 무게 조건 이라면 다리로 올라갈 수 있다.
            if (trucksOnBridge.size() < bridge_length && totalWeight + currentTruck <= weight)
            {
                trucksOnBridge.push({ currentTruck, current }); // 다리에 올라간 것을 표현
                totalWeight += currentTruck;                    // 총 무게에 현재 트럭의 무게를 더해준다.
                 ++truckIdx;                                    // 다음 트럭을 가리킴
            }
        }
        
        ++current;  // 시간이 1 경과한다.
    }
        
    answer = current - 1;   // 마지막 차례에서 ++current; 한 거를 빼줘야 한다.
    
    return answer;
}