[프로그래머스/Level2] 다리를 지나는 트럭 (C++)

ziwon.k·2021년 6월 22일

[프로그래머스] 연습문제

목록 보기

5/10

1.문제

2. 접근/체크포인트

주어진 대기 순서대로 다리를 건너게 해야함 -> 큐 사용.

한 자동차가 다리를 건너는 동안 무게를 견딜 수 있다면 다음 자동차도 이어서 다리를 건너야 함.

마지막 자동차 순서에는 다리 길이만큼 + 해서 건너는 시간 계산.

3. 해결 방법

truck_weights에서 자동차를 선택하기 위한 idx변수 사용.

현재 다리를 건너고 있는 자동차들의 무게를 계산하기 위한 sum 변수 사용.

현재 다리를 건너고 있는 자동차들을 체크하고, 자동차들이 다리를 건너는 시간을 계산하기 위한 큐 사용.

새로운 자동차가 다리에 진입할 때 +1초

새로운 자동차 진입 후, 대기중인 다음 자동차의 무게와 현재까지 진입한 자동차의 총 무게가 weight(다리가 견딜 수 있는 총 무게) 보다 작거나 같다면, 대기중인 다음 자동차 진입.
5-1. 다음 자동차가 진입할 수 없다면 현재 진입한 자동차가 건너는 시간 count를 위해 큐에 0을 push

큐의 크기가 다리의 크기와 같아진다면 = 차가 다리를 다 건넜다면, 현재 총 무게에서 다 건너간 자동차의 무게를 제외하고, 다음 차량이 건널 수 있도록 idx를 증가 시킨다.
7.위위 과정들을 반복하다, idx가 마지막 차량을 가리킬 때(idx==truck_weights.size()) answer에 다리의 길이를 +함으로써, 마지막 차량이 건너가는 시간까지 계산해준다.

4.전체코드

#include <queue>
#include <vector>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    
    int idx=0;    //차량 지목용 idx
    int sum=0;   //현재 다리에 올라와있는 차량 무게 총합
    queue<int> q;  //현재 다리를 건너는 트럭 체크용 큐
    
    while(1){
        
        if(idx == truck_weights.size()){  //마지막 트럭일 때
            answer += bridge_length;  //마지막 트럭이 지나는 시간 추가
            break;  
        }
        
        answer++; //시간초 증가
        int tmp = truck_weights[idx];
        
        //차가 다리를 다 건넜을 경우
        if(q.size() == bridge_length){
            sum -= q.front();  //다 건넜으니 현재 다리에 있는 차들의 무게에서 제외
            q.pop();  
        }
        
        if(sum + tmp <= weight){  //다리에 다음 차가 진입할 수 있다면
            sum += tmp;  //차량 무게 추가
            q.push(tmp);  
            idx++;  //다음 차량을 위해서
        }else{   
            q.push(0);  //진입할 수 없다면 0을 푸시해서 시간초 계산
        }
    }
   
    return answer;
}