[C++][프로그래머스] 다리를 지나는 트럭 rotate(), q.back()

프로그래머스

 

📄 문제

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

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

 

📝 풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int n = truck_weights.size();
    
    vector<int> v(bridge_length + 1, 0);
    int sum = 0;
    int idx = 0;
    
    while(idx < n)
    {
        // 왼쪽으로 한칸씩 이동
        rotate(v.rbegin(), v.rbegin() + 1, v.rend());
        
		// 마지막에 있는 트럭을 내보내기
		sum -= v[bridge_length]; // 마지막에 있는 트럭의 무게를 빼기
		v[bridge_length] = 0; // 해당 값은 0으로 설정        
        
		// 트랙 보내기 시도
		if (sum + truck_weights[idx] <= weight)
		{
			v[0] = truck_weights[idx++];
			sum += v[0];
		}

		++answer;
    }
    
    for(int i = 0; i < bridge_length; ++i)
        if(v[i])
        {
            answer += bridge_length - i;
            break;
        }
    
    return answer;
}

• rotate 함수를 이용하여 문제를 해결하였습니다.
  • (인덱스가 1에서 0로) 한칸씩 이동 rotate(v.begin(), v.begin() + 1, v.end());
  • (인덱스가 0에서 1로) 한칸씩 이동 rotate(v.rbegin(), v.rbegin() + 1, v.rend());
• 트럭의 무게를 0부터 삽입하여 brigde_length까지 회전하여 더합니다.
• v[brigde_length]에 값이 있다면, 트럭이 다리를 모두 지난것으로, sum에서 빼줍니다.
• 매 반복문마다 검사하여 트럭의 무게를 삽입하고, 종단에서 트럭을 빼줌으로써 문제를 해결하였습니다.

 

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    queue<pair<int, int>> q;
    int sum = 0; // 현재 다리에 있는 트럭의 무게 합
    int idx = 0; // 삽입할 인덱스 번호
    int time = 0; // 경과된 시간
    int n = truck_weights.size(); // 트럭의 개수
    
    while(idx < n)
    {
        // q가 비어있지 않으면서, q의 front의 시간이 경과되었다면? (도착)
        if(!q.empty() && time >= q.front().second)
        {
            sum -= q.front().first; // 무게에서 빼기
            q.pop(); // 큐에서 제거
        }
        
        // idx번째의 트럭을 다리에 둘 수 있는가? (무게를 초과하지 않는가?)
        if(sum + truck_weights[idx] <= weight)
        {
            q.push({truck_weights[idx], time + bridge_length}); // 큐에 트럭의 무게와 도착 예정 시간 삽입
            sum += truck_weights[idx++]; // 무게 합
        }
        
        ++time; // 시간 경과
    }
    
    // 큐의 가장 마지막 원소의 시간 + 1을 리턴
    return q.back().second + 1;
}

• 큐를 이용하여 문제를 해결합니다.
• 큐에 차례대로 삽입을 시도합니다. 이때, 총 합의 무게가 weight를 넘어서는 안됩니다.
• time을 지속적으로 증가하여 만약, 큐의 front의 second(도착 예정 시간)이 time 이상이라면, 도착을 한 경우로 sum에서 first(무게)를 제거하고, 큐에서 제거합니다.
• 모든 idx를 삽입하였다면, q.back().second + 1을 리턴합니다. 이 과정은 다리 위에서 가장 늦게 삽입된 트럭이 도착하는 시간을 더한 값입니다.