[프로그래머스] 다리를 지나는 트럭

 

 

■ 문제 설명

 

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

 

solution 함수의 매개변수로 다리 길이 bridgelength, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truckweights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

 

■ 제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

■ 입출력 예

bridge_length	weight	truck_weights	return
2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

 

 

▶ 코드

 

코드를 짤 때 키가되는 아이디어는 다음과 같다.

 

1. 다리위에 새로운 트럭을 수용 할 수있으면 큐에 대기 트럭을 push한다.

2. 그렇지 않다면 큐에 0을 push 한다. 

트럭의 무게는 1이상이여야 하므로 0은 다리위에 있는 트럭의 무게에 영향을 주지 않으면서,

동시에 index 역할을 할 수 있다.

 

처음에 0을 생각하지 못해 헤맸는데 0으로 하니 생각보다 쉽게 풀렸던 문제였다.

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int sum =0; //다리 위에 현재 트럭의 무게
    queue<int> q;

    vector<int>::iterator iter = truck_weights.begin();


    while(true){

        /* 1.건너야할 트럭이 없음 
        & 다리위에 모든 트럭이 다 건넜음(다리위의 트럭을 표시하는 queue가 비었음) 
        => return */
        if(iter == truck_weights.end()){
            while(q.size() != bridge_length){
                q.push(0);
            }
            while(!q.empty()){
                answer++; q.pop();
            }
            return answer;
        }

        /* 2. 건너야할 트럭이 있음 */
        // i) 다리위의 트럭이 꽉 차있는 경우
        if(q.size() == bridge_length){
            sum-=q.front(); q.pop();
        }

        //ii) 다리위의 트럭이 꽉 차지 않은 경우
        if(sum + *iter <= weight) { //트럭의 무게 수용 가능
            q.push(*iter);
            answer++; sum+=*iter;iter++;
        }else{ //수용 불가
            answer++;  q.push(0);
        }
    }
}

 

 

 

※ 출처 : https://programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스