알고리즘 3일 차
늘 그렇듯이 문제를 해석하는게 일이지만 다행이도 해석하는게 어렵지는 않았다.
bridge_length=2, weight=10, truck_weight=[7, 4, 5, 6]
bridge_length가 2이므로 다리는 2칸이다.
weight가 10이므로 다리가 버틸 수 있는 최대 무게는 10이다.
문제를 이해했으니 문제를 해결해 보자
다음은 내가 참고한 블로그이다. https://minhamina.tistory.com/241
import java.util.*;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
Queue<Integer> queue = new LinkedList<>();
int sum = 0;
int time = 0;
for(int i = 0; i < truck_weights.length; i++) {
int truck = truck_weights[i];
while(true) {
if(queue.isEmpty()) {
queue.add(truck);
sum += truck;
time++;
break;
} else if(queue.size() == bridge_length) {
sum -= queue.poll();
} else {
if(sum + truck <= weight) {
queue.add(truck);
sum += truck;
time++;
break;
} else {
queue.add(0);
time++;
}
}
}
}
return time + bridge_length;
}
}
내가 해석한 내용이다.
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
Queue<Integer> queue = new LinkedList<>();
int sum = 0;
int time = 0;
int bridge_length, int weight, int truck_weights 리스트를 받는다.
queue라는 이름의 queue 리스트를 만든다.
int sum, int time은 0이다.
for(int i = 0; i < truck_weights.length; i++) {
int truck = truck_weights[i];
i는 0이고 truck_weights의 길이보다 i보다 작거나 같을 때까지 i는 1씩 증가한다.(for)
truck은 truck_weights의 리스트들이다.
while(true) {
if(queue.isEmpty()) {
queue.add(truck);
sum += truck;
time++;
break;
} else if(queue.size() == bridge_length) {
sum -= queue.poll();
} else {
if(sum + truck <= weight) {
queue.add(truck);
sum += truck;
time++;
break;
} else {
queue.add(0);
time++;
}
}
}
문장을 무한 반복한다.(while)
만약 queue가 비어있다면
queue에 트럭을 올려준다.
sum에 truck무게를 추가한다.
time에 +1을 한다.
while문을 나간다.
또는 queue의 사이즈와 다리의 길이가 같다면
sum에서 queue의 맨 앞 데이터를 제거한다.
그 외에는
만약 sum과 truck의 합이 weight보다 작거나 같으면
queue에 truck을 올린다.
sum에 truck무게를 추가한다.
time에 1을 추가한다.
while문을 나간다.
그 외에는
queue에 빈칸을 올린다.
time에 1을 추가한다.
return time + bridge_length;
time(지금까지 걸린 시간)과 bridge_length(마지막 트럭이 건너는데 걸리는 시간)를 합친 값을 반환해준다.
재밌다