import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
Queue<Integer> bridge = new LinkedList<>();
int time = 0;
int total = 0;
int index = 0;
for (int i = 0; i < bridge_length; i++) {
bridge.add(0);
}
while (index < truck_weights.length) {
time++;
int truckLeaving = bridge.poll();
total -= truckLeaving;
if (total + truck_weights[index] <= weight) {
bridge.add(truck_weights[index]);
total += truck_weights[index];
index++;
} else {
bridge.add(0);
}
}
time += bridge_length;
return time;
}
}
이 문제는 트럭들이 다리를 건너는 문제로 해당 조건에 맞춰야한다.
1. 다리의 길이(bridge_length) 만큼 트럭들이 다리를 건너야 한다.
2. 다리가 견딜 수 있는 최대 무게(weight)를 초과하지 않도록 트럭들을 다리 위에 올려야 한다.
3. 트럭들이 다리 위에 올라가고, 다리를 다 건넌 시간도 고려해야 한다.
이 3가지 조건을 맞춰서 코드를 작성해야 한다.
코드 분석
Queue<Integer> bridge = new LinkedList<>();
int time = 0;
int totalWeightOnBridge = 0;
int index = 0;
1. 먼저 다리를 큐로 표현 하고 트럭들이 다리 위에 있는 상태를 관리해준다.
- time : 경과한 시간을 기록
- total : 현재 다리 위에 있는 트럭들의 총 무게를 기록
- index : 대기 중인 트럭들의 인덱스를 관리
for (int i = 0; i < bridge_length; i++) {
bridge.add(0);
}
for 문을 이용하여 다리를 초기화 한다. 다리 길이 만큼 0을 넣어 다리에 트럭이 없도록 해야한다.
// 모든 트럭이 다리를 건널 때까지 반복
while (index < truck_weights.length) {
// 시간 증가
time++;
// 다리에서 트럭 하나 제거 (다리를 다 건넌 트럭)
int truckLeaving = bridge.poll();
totalWeightOnBridge -= truckLeaving;
// 다음 트럭이 다리에 올라갈 수 있는지 확인
if (totalWeightOnBridge + truck_weights[index] <= weight) {
// 다리에 트럭 추가
bridge.add(truck_weights[index]);
totalWeightOnBridge += truck_weights[index];
index++;
} else {
// 다음 트럭이 다리에 올라갈 수 없으면 0 추가 (빈 자리)
bridge.add(0);
}
}
for문을 사용해도 되지만 for문은 구하고자 하는 값의 조건이 무엇인지 정확할 경우에 사용되지만 while문을 이용하면 블록에서 바로 찾을 수 있기 때문에 가독성이 좋아 while문을 이용했다.
while문을 이용하여 false가 나올때까지 게속 동작 되고 만약 더 이상 트럭이 다리에 올라갈 수 없으면 0을 추가해준다.
마지막으로 time += bridge_length 해주면서 마지막 트럭들이 다리를 건너는 시간을 추가해준다.
다른 사람 코드
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
Stack<Integer> truckStack = new Stack<>();
Map<Integer, Integer> bridgeMap = new HashMap<>();
for (int i = truck_weights.length-1; i >= 0; i--)
truckStack.push(truck_weights[i]);
int answer = 0;
int sum = 0;
while(true) {
answer++;
if (bridgeMap.containsKey(answer))
bridgeMap.remove(answer);
sum = bridgeMap.values().stream().mapToInt(Number::intValue).sum();
if (!truckStack.isEmpty())
if (sum + truckStack.peek() <= weight)
bridgeMap.put(answer + bridge_length, truckStack.pop());
if (bridgeMap.isEmpty() && truckStack.isEmpty())
break;
}
return answer;
}
}
문제의 포인트
이 문제는 모든 트럭이 다리를 건너기 위해 필요한 최소 시간을 계산하는 것이다. 하나씩 다리를 건너야 하는데 스택과 큐 중 큐가 가장 적합하다고 생각했다.
그렇다면 다리의 길이와 걸리는 시간 그리고 트럭을 추가 및 제거 를 반복적으로 해줘서 최종 시간을 계산을 해야한다.
위의 코드를 보면 add 를 사용했다. offer 를 사용해도 되는데 왜 add를 사용했을까?
add 는 큐가 제한을 초과하면 요소를 추가할 수 없으면 IllegalStateException(예외) 을 던지지만 offer는 초과하는 경우 false를 반환다. 어떻게 보면 offer가 좋지만 만약 크기에 제한이 걸려있으면 offer가 좋고 만약 제한이 안걸려 있으면 add를 사용한다.
따라서 add 보단느 offer를 사용하는것이 더 안전한 코드가 된다.