문제 링크
풀이
(int) bridge_length
= 다리 길이
(int) weight
= 다리가 견딜 수 있는 트럭 무게의 합
(int[]) trucks_wieght
= 트럭의 무게들이 기록되어있는 Array
주요 변수
total_time
: 모든 트럭이 다리를 건너는데 걸린 시간을 담고있음
weight_sum
: 다리에 올라간 트럭 무게의 총합을 담고있음
truck_idx
: truck_weights Array에서의 idx를 의미하며, 트럭이 다리에 올라갔는지 & 다리가 견딜 수 있는 무게(=weight) 값이랑 비교하기 위해 쓰인다.
로직
- 다리(bridge)를 표현할 0으로 채워진 Queue를 만들어준다
- Queue의 크기(size) = 다리의 길이(
bridge_length)
=> bridge_queue
Queue<Integer> bridge_que = new LinkedList<>();
for (int i = 0; i < bridge_length; i++) {
bridge_que.offer(0);
}
while문
을 통해서 트럭이 다리를 건너는 상황을 시뮬레이션 할 수 있도록해준다
while문
한번돌때마다 1초임 = 트럭이 한칸씩 움직임
while문
조건 : bridge_que
가 비었는지 확인
- 비었다면 트럭이 모드 건넜다는 뜻 = while문 멈춘다
while문
내에서 로직
- 다리를 건너게 함 :
bridge_que
맨앞에 있는 값을 뽑아냄(bridge.offer()
)
- 현재 다리위에 있는 트럭들의 무게 = 현재 다리위에 있는 트럭들의 무게 - 이번에 건너는 무게(트럭무게 or 0)
- 현재 다리위에 있는 트럭들의 무게 + 이번에 올리고자하는 트럭의 무게 <= 다리가 견딜 수 있는 트럭 무게의 합
- 트럭을 올릴 수 있다면 =>
bridge_que
에 트럭의 무게값
을 넣어준다
- 트럭을 올릴 수 없다면 =>
bridge_que
에 0
을 넣어준다
while (!bridge_que.isEmpty()) {
int popped = bridge_que.poll();
weight_sum -= popped;
if (truck_idx < truck_weights.length) {
if (weight_sum + truck_weights[truck_idx] <= weight) {
bridge_que.offer(truck_weights[truck_idx]);
weight_sum += truck_weights[truck_idx];
truck_idx++;
} else {
bridge_que.offer(0);
}
}
total_time++;
}
전체 코드