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

문제

programmers.co.kr/learn/courses/30/lessons/42583

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

---

코드

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int now_weight = 0;
    int i = 0;
    queue<pair<int, int>> bridge;
    
    while(1)
    {
        ++answer;
        if (!bridge.empty() && answer - bridge.front().second == bridge_length)
        {
            int tmp = bridge.front().first;
            bridge.pop();
            now_weight -= tmp;
        }
        if (i < truck_weights.size() && now_weight + truck_weights[i] <= weight)
        {
            bridge.push(make_pair(truck_weights[i], answer));
            now_weight += truck_weights[i];
            ++i;
        }
        if(bridge.empty())
            break;
    }
    return answer;
}

우선 전체적인 흐름은 while문이 계속 돌아가면서 answer(시간)이 증가된다. now_weight변수는 현재 다리위에 있는 트럭들의 무게의 합이다. 큐 bridege에는 트럭의 무게와 트럭이 다리위에 올라간 시점도 함께 저장해준다. 

 

첫번째 조건문에서는 bridge에 들어있는 트럭이 다리를 다 지나갔을때, bridge에서 pop해주고, now_weight에서도 트럭의 무게를 빼준다. 트럭이 다리를 다 지나갔는지에 대한 판별은, 현재 흘러간 시간을 나타내는 answer에서 다리가 올라간 시점인 bridge.front()의 second를 빼준 결과가 bridge_length가 나오는지로 결정된다. 

        if (!bridge.empty() && answer - bridge.front().second == bridge_length)
        {
            int tmp = bridge.front().first;
            bridge.pop();
            now_weight -= tmp;
        }

 

두번째 조건문에서는 다리위에 트럭을 올리는 과정이다. 올라가야하는 트럭의 index를 나타내는 i가 벡터의 사이즈보다 작고, now_weight에 i번째 트럭을 올렸을때 주어진 weight보다 작은지 판별한다. 조건을 만족할 경우에 큐 bridge에는 트럭의 무게와 현재 시간인 answer을 모두 push해준다. 

        if (i < truck_weights.size() && now_weight + truck_weights[i] <= weight)
        {
            bridge.push(make_pair(truck_weights[i], answer));
            now_weight += truck_weights[i];
            ++i;
        }

 

마지막 조건문은 while문을 탈출시켜주는 조건이다. 큐 bridge가 비면 while문을 종료시켜준다. while문에 한번 들어오면 마지막 트럭이 빠져나가지 않는 이상, bridge에는 항상 트럭이 존재한다. while문의 조건으로 bridge.empty를 넣어버리면 while문에 들어올 수 없기 때문에 따로 while문 안에서 if문을 작성해주었다.

이 문제에서는, while문 안에서 조건들의 순서가 매우 중요하다❗️❗️❗️처음에 이것 때문에 값이 조금씩 다르게 나왔다. 트럭이 먼저 빠지고 난 후에 다음 트럭이 올라간다. 따라서 첫번째 조건문에 트럭이 빠져나가는 코드가 들어가야한다. 또한, 세 조건문은 if, else if으로 묶이는 것이 아니라, 각각 if문으로 처리해주어야한다. 트럭이 빠져나가는 사건, 트럭이 다리위에 올라가는 사건, 그리고 while문이 끝나는 조건이 동시에 일어날 수 있기 때문이다.