[프로그래머스] 다리를 지나는 트럭 (level 2, 큐/스택)

문제

프로그래머스 문제 보기

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다.

모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다.

트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다.

무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다.

이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제약조건

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

풀이

큐를 써서 풀어야 하는 간단한 문제다. 다리가 견딜 수 있는 하중에 한계가 있다는 제약조건을 고려하며 문제를 풀면 간단하다.

다리에 실리는 하중이 한계치보다 작은 선에서 최대한 많은 차를 빨리 다리 위로 올리면 최소 시간에 다리를 건널 수 있다.

문제를 풀기 위해 다리를 건너는 중인 트럭의 무게와 시간을 저장하는 큐 두 개(entered_weights, times)를 사용하였다.

이 때 다리에 들어선 트럭의 무게를 각각 기록하여 큐 entered_weights에 삽입한다. 이를 통해 트럭이 다리를 다 건넜을 때 큐를 pop하여 삭제하여 다리의 하중치에서 도착한 차의 무게를 덜어낼 수 있다.

또한 이 때 truck_weights는 대기트럭의 목록으로 보아 맨 앞에 있는 원소를 삭제해준다.

다리에 새로운 트럭이 들어오는 시간을 또 다른 큐 times에 삽입 하여 기록해주면 차의 속도가 일정하므로 트럭이 다리를 다 건너는 시간 또한 알 수 있다. 마찬가지로 다리를 다 건너면 큐를 pop해주면 된다.

entered_weights와 trucks_weights가 모두 비는 경우, 즉 모든 트럭이 다리를 다 건너게 되는 경우에는 가장 마지막으로 트럭이 도착한 시간이 문제의 답이 된다.

소스코드

언어는 C++을 사용했다.

#include <string>
#include <queue>
#include <vector>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int weight_now = 0;
    queue<int> times, entered_weights;
    for(int i=1;;i++)
    {
       if(times.size()>0)
       {
       		// 다리의 맨 앞에 있던 트럭이 다리를 다 건넜을 때
           if(i - times.front()==bridge_length)
           {
           		// 트럭이 다리를 다 건널 때 마다 도착한 시간을(출발한 시간 + 다리 길이) 갱신해준다.
               int finish_time = bridge_length + times.front();
               // 다 건넌 트럭의 정보를 삭제해주고 다리가 견디는 무게도 갱신한다.
               times.pop();
               weight_now -= entered_weights.front();
               entered_weights.pop();
			   //건너야할 트럭이 더 이상 없고 건너는 중인 트럭도 없을 때
               if(truck_weights.size()==0&&entered_weights.size()==0)
               {
               		//마지막 트럭이 들어간 시간을 리턴한다.
                   return finish_time; 
               }
           }
       }
        //다리의 한계 하중치를 초과하기 전까지 트럭을 다리 위로 올린다.
        while(1)
        {
        	// 다리에 트럭이 더 들어서지 못하거나 더 이상 들어설 트럭이 없으면 break
            if(weight_now+truck_weights.front()>weight
               ||truck_weights.size()==0)
            {
                break;
            }
            else{
            	// 다리에 들어온 트럭의 무게가 추가된다.
                weight_now += truck_weights.front();
                // 다리에 들어온 트럭의 무게와 들어온 시간을 기록한다.
                entered_weights.push(truck_weights.front());
                times.push(i);
                truck_weights.erase(truck_weights.begin());
                break;
            }
        }
        
    }
}