[프로그래머스] 다리를 지나는 트럭 C++ 풀이 및 해설

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

프로그래머스

 

풀이 방법

아래의 로직을 수행하자.

 

1. 다리의 트럭들이 한 블럭씩 이동한다. (이때 다리를 모두 건넌 트럭은 pop한다.)

2. 다리에 오를 수 있는 트럭들을 다리에 추가한다.

3. 시간을 +1 해준다.

 

123 과정을 트럭들이 다리를 모두 건널때까지 반복해주면 된다.

 

전체 코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    queue<pair<int,int>> q;
    
    // 큐에 넣을때 위치를 0인지 1인지, 이동후 다리를 건너는중 기준은 <=인지 <인지
    
    int curWeight = 0;
    int i=0;
    while(i<truck_weights.size()) {
        
        int qSize = q.size(); // 한 사이클만 돌게 큐 크기 저장
        for(int i=0; i<qSize; i++) { // 다리 위 트럭 이동
            if(!q.empty()) {
                int weight = q.front().first;
                int cnt = q.front().second;
                q.pop();
                if(cnt+1<=bridge_length) { // 다리를 건너는중
                    q.push(make_pair(weight,cnt+1)); // 트럭 1칸 이동
                } else { // 다리를 건넘, 총무게 감소
                    curWeight-=weight;
                }
            }
        }
        
        
        if(curWeight+truck_weights[i] <= weight && q.size()+1<=bridge_length) { // 다리에 올라설 수 있으면
            q.push(make_pair(truck_weights[i], 1)); // 큐에 트럭 추가 아래에 1초를 경과 처리할건데 그때 위치는 1초가 지났으니 1의 위치에 있어야함. 그래서 위치 1로 넣어줌
            curWeight+=truck_weights[i]; // 총무게에 트럭 무게 추가
            i++;
        }     
        
        answer++;
    }
    
    
    // 위의 while문은 마지막 트럭이 다리에 오르는 순간 모든 트럭이 다리에 올랐으므로
    // 반복문을 돌지 않게 된다. 이때 다리에 트럭들이 남아 있으므로
    // 아래의 while문으로 남은 트럭들이 이동하는데 시간을 계산해주자.
    while(!q.empty()) {
        int qSize = q.size(); // 한 사이클만 돌게 큐 크기 저장
        for(int i=0; i<qSize; i++) { // 다리 위 트럭 이동
            if(!q.empty()) {
                int weight = q.front().first;
                int cnt = q.front().second;
                q.pop();
                if(cnt+1<=bridge_length) { // 다리를 건너는중
                    q.push(make_pair(weight,cnt+1)); // 트럭 1칸 이동
                } else { // 다리를 건넘, 총무게 감소
                    curWeight-=weight;
                }
            }
        }
        answer++;
    }
    
    return answer;
}