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

프로그래머스 42583 - 다리를 지나는 트럭

문제 링크

생각 및 접근

• 문제의 접근은 이렇게 했습니다.
  • 시간을 1초씩 늘려가는 while문을 돌려야겠다.
  • while문을 돌면서 다리 위를 건너는 트럭의 남은 다리 길이를 1씩 줄여야겠다.
  • 다리 위를 건너는 트럭을 큐에 저장해야겠다.
• queue< pair<int, int> > crossing
  • 다리 위를 지나가는 트럭을 저장하는 큐에는 트럭의 무게와 트럭의 남은 다리 길이를 저장해야 했습니다.
  • pair의 왼쪽은 트럭의 무게를, pair의 오른쪽은 트럭의 남은 다리 길이를 저장했습니다.
  • 큐를 순회하면서, 길이를 하나씩 줄여줍니다. 길이가 1이였다면, 그 트럭은 다리를 지난 트럭이 되므로 다리 위 전체 트럭의 무게를 저장하고 있던 onWeight에서 트럭의 무게를 빼줍니다.
• 트럭을 큐에 넣는 조건
  • 대기하고 있는 트럭이 있고,
  • 대기하고 있는 트럭의 무게 + onWeight가 다리 최대 무게를 넘지 않아야 합니다.
• 무한루프를 빠져나오는 조건
  • 더이상 대기하고 있는 트럭이 없고,
  • 다리를 지나고 있는 트럭 또한 없으면 됩니다.
• 시간을 저장하는 변수 answer
  • while문이 끝나기 전에 answer++; 해줍니다.

코드

#include <bits/stdc++.h>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0, onWeight = 0, waitingIndex = 0;
    queue< pair<int, int> > crossing;

    while(-1){
        int crossingNum = crossing.size();

        for(int i = 0; i < crossingNum; i++){
            int wei = crossing.front().first;
            int len = crossing.front().second;
            crossing.pop();

            if(len <= 1){
                onWeight -= wei;
                continue;
            }
            crossing.push(make_pair(wei, len - 1));
        }

        if(waitingIndex < truck_weights.size() && onWeight + truck_weights[waitingIndex] <= weight){
            crossing.push(make_pair(truck_weights[waitingIndex], bridge_length));
            onWeight += truck_weights[waitingIndex];
            waitingIndex++;
        }

        answer++;

        if(waitingIndex >= truck_weights.size() && crossing.empty())
            break;
    }    
    return answer;
}

채점 결과