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

1. 문제

일차선의 다리의 길이, 다리가 견딜 수 있는 무게가 주어진다.

 

트럭이 주어진 순서대로 1초에 다리 길이 1 만큼 움직인다고 할때

 

최소 걸리는 시간을 구하여라.

 

2. 자료구조 queue

 

제한 무게 10인 다리에 트럭이 다음과 같은 순서로 온다고 해보자

 

7, 4, 5, 6

 

그럼 다음과 같이 나타낼 수 있다

 

							7
						7	0
					7	0	4
				7	0	4	5
			7	0	4	5	0
		7	0	4	5	0	6
	7	0	4	5	0	6	0
7	0	4	5	0	6	0	0
답: 8

 

빨간색 이 다리위에 있는 트럭들을 보여준다.

 

결과로 나오는 배열 7, 0, 4, 5, 0, 6, 0, 0

의 크기가 정답이 됨을 알 수 있다.

 

그러므로 주어진 순서에 맞게 큐에 집어넣으면서 만약 무게가 초과되면 0인 더미 값을 집어넣고 길이가 초과되면 pop하면 정답을 쉽게 얻어낼 수 있다.

 

하지만 이런 방식은 느리다. 그리고 0 인 더미를 연속으로 집어 넣는건 비효율적이다.

 

3. 건너뛰기

-큐에 더미의 정보를 압축하여 pair에 저장한다.  이는 결과 배열의 인덱스 값 + 1 과 같다. 즉, 결과 배열의 해당 위치를 저장하는것

 

-그러면 더미를 추가하는 작업없이 트럭의 개수가 n 이면 O(n)번의 검사만에 끝을 낼 수 있다.

 

-트럭무게 벡터 마지막에 다리 가 견딜 수 있는 값을 추가하면 맨 끝원소까지 자연스럽게 문제를 해결할 수 있다.

 

-맨 앞 트럭이 마지막 다리를 건널때 POP해주는것을 잊지말자 ( 길이 초과)

 

- move = bridge_length - (answer - thisPos) :  결과배열과  다리를 나가는 지점까지 상대적 위치를 계산한다

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0, capa = 0, move = 0;
    queue<pair<int, int> > q;
    truck_weights.push_back(weight);
 
    for(int i = 0; i < truck_weights.size(); i++)
    {
        bool isMove = false;
        while(capa + truck_weights[i] > weight )
        { 
            capa -= q.front().second;    
            move = bridge_length - (answer - q.front().first);
            answer += move;
            q.pop();
            isMove = true;
        }
        if((!q.empty())&&(1 == bridge_length - (answer - q.front().first)))
        { 
            capa -= q.front().second;
            q.pop();
        }
        if(!isMove) answer++;
        capa += truck_weights[i];
        q.push(make_pair(answer, truck_weights[i]));
    }
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/42583

github.com/Nor-s/Algorithm/blob/master/programmers/Trucks.cpp