큐 - 다리를 지나는 트럭
Updated:
C++
스택/큐 - 프린터
문제
solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.
접근 방법
다리를 queue라고 생각하고 truck을 그 queue에 들어가는 숫자라고 생각을 한다.
그렇다면 최대 queue의 크기는 bridge_length가 될 것이고, 그 이상의 truck이 push 되려하면 제일 앞의 truck을 pop한다.
하지만 여기서 의문점이, 다리 위에 주어진 무게는 최대 weight이다. 이는 가짜 트럭을 넣는 것으로 생각한다
즉 만약 대기 순서의 트럭이, 현재 다리 위에 있는 트럭의 총 무게로 인하여 갈 수 없을 때, 크기가 0인 가상의 트럭을 queue 다리에 대신 넣는다.
이렇게 되면, queue의 크기가 지속적으로 최대 크기로 유지 되며, 제일 앞의 트럭이 빠져 나갈 때 진짜 트럭일 시 다리 위 무게가 줄어들게 하여, 다음 진짜 트럭을 보낼 수 있게 한다.
만약 대기 순서에 있는 모든 진짜 트럭이 다리에 올라가면, 종료하고 여태동안 걸린 총 시간을 계산하며 종료한다.
구현
총 걸린 시간을 time으로, while문을 돌 때마다 time을 증가시킨다.
truck_weights인 대기 목록의 트럭을 하나씩 가져온다. 이는 idx로 구분한다.
가져온 트럭의 무게와 현재 다리의 무게의 합이 weigth보다 작으면 다리를 나타내는 bridge에 추가한다.
무게의 합이 넘으면, 현재 트럭이 올라 올 수 없으므로 가상의 트럭을 bridge에 추가하며 이의 무게는 0이다.
bridge가 bridge_length와 같아지면, 다리가 꽉 찼으므로 제일 앞의 truck의 weight을 뺀다.
만약 진짜 truck이면 무게가 빠질것이며, 가짜 트럭이면 0이므로 무게의 변화는 없다.
idx가 총 truck_weights의 size와 같아지면 while문을 종료한다.
이 조건문이 true일 때는, 마지막 트럭이 막 다리에 진입한 것이므로, 총 다리의 크기를 더 해주어 총 걸린 시간을 계산한다.
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0, time = 0;
int idx = 0; //대기 트럭의 순서를 나타내는 index
int sum = 0; //다리 위의 무게
queue<int> bridge;
while (1) {
if (truck_weights.size() == idx) { //종료 조건
time += bridge_length; //주어진 트럭 개수 만큼 뽑았을 때, 마지막 트럭은 다리 위를 출발하므로 다리 길이 만큼 더해주고 종료한다.
break;
}
time++; //1초 증가
int curT = truck_weights[idx]; //대기 목록의 트럭을 나열한다.
if (bridge_length == bridge.size()) { // 가짜 트럭 포함, 총 트럭이 다리 위에 꽉차 있을 시, 앞에서 부터 제거한다.
sum -= bridge.front(); // 트럭이 빠져 나갔으므로 무게를 뺀다. 만약 가짜 트럭이면 0을 빼므로 무게 차이는 없다.
bridge.pop();
}
if (sum + curT <= weight) { //대기 순서의 트럭이 현재 다리 위의 무게보다 적으면 진짜 트럭을 올린다.
sum += curT;
idx++;
bridge.push(curT);
}
else { //올릴 수 없으면, 가짜 트럭이며 크기가 0인 트럭을 다리 위에 올린다.
bridge.push(0);
}
}
answer = time;
return answer;
}
후기 및 개선할 점
직접 푸는 문제는 결국 해결하지 못하고, 타인의 해답을 참고하였다.
