[Programmers] 다리를 지나는 트럭
문제 설명
트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.
solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.
제한 사항
- bridge_length는 1 이상 10,000 이하입니다.
- weight는 1 이상 10,000 이하입니다.
- truck_weights의 길이는 1 이상 10,000 이하입니다.
- 모든 트럭의 무게는 1 이상 weight 이하입니다.
소스코드
C++
#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, idx = 0;
queue<int> q;
while(1) {
answer++;
// 큐의 길이와 다리의 길이가 같으면 트럭이 도착한 것
if(q.size() == bridge_length) {
sum -= q.front();
q.pop();
}
// 다음 트럭이 다리를 지나갈 수 있으면
// 다음 트럭의 무게를 더한 합이 다리의 무게보다 작으면, 트럭 push
if(sum + truck_weights[idx] <= weight) {
// 마지막 트럭이면 마지막 트럭의 길이만큼 시간을 더해준다.
if(idx == truck_weights.size()-1) {
answer += bridge_length;
break;
}
q.push(truck_weights[idx]);
sum += truck_weights[idx];
idx++;
}
// 다음 트럭의 무게를 더한 합이 다리의 무게보다 크면 0을 push해
// 트럭의 도착 시간을 맞춰준다.
else {
q.push(0);
}
}
return answer;
}
Java
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
int answer = 0;
int sum = 0, i = 0;
Queue<Integer> q = new LinkedList<>();
for(int truck : truck_weights) {
while(true) { // 트럭 올릴 때 까지 반복
answer += 1;
// 큐가 비어있으면 다리에 트럭 올림.
if(q.isEmpty()) {
q.add(truck);
sum += truck;
break;
}
// 다리에 트럭이 최대로 올라가면 큐에서 제거
if(q.size() == bridge_length) {
sum -= q.poll();
}
// 다리에 트럭 더 올릴 수 있으면 큐에 추가
if(sum + truck <= weight) {
q.add(truck);
sum += truck;
break;
}
// 못 올리면 0 추가
else {
q.add(0);
}
}
}
return answer + bridge_length;
}
}
소감
0을 push해주는게 포인트였다,,
그리고 마지막 트럭이 건너는 시간을 추가해줘야한다!!
Author And Source
이 문제에 관하여([Programmers] 다리를 지나는 트럭), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@minwest/Programmers-다리를-지나는-트럭저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)