문제
내 코드
private static int solution(int bridge_length, int bridge_weight, int[] truck_weights) {
int time = 0;
int truck_cnt = truck_weights.length;
//1
Queue<Truck> on_bridge = new LinkedList<Truck>();
Queue<Truck> complete = new LinkedList<Truck>();
Queue<Truck> waiting = new LinkedList<Truck>();
for (int w : truck_weights) {
waiting.offer(new Truck(bridge_length, w));
}
//2
int cur_total_weight = 0;
while (complete.size() != truck_cnt) {
System.out.println("time : " + time);
//3
if(!on_bridge.isEmpty()){
if (on_bridge.peek().time == 0){
cur_total_weight -= on_bridge.peek().weight;
complete.offer(on_bridge.poll());
}
}
//4
if (cur_total_weight <= bridge_weight && on_bridge.size() <= bridge_length) {
if (!waiting.isEmpty()) {
if (cur_total_weight + waiting.peek().weight <= bridge_weight && on_bridge.size() + 1 <= bridge_length) {
cur_total_weight += waiting.peek().weight;
System.out.println(waiting.peek().weight);
on_bridge.offer(waiting.poll());
}
}
}
//5
int temp_size = on_bridge.size();
for(int i=0; i<temp_size; i++){
Truck tempTruck = on_bridge.poll();
tempTruck.time = tempTruck.time - 1;
on_bridge.offer(tempTruck);
}
time++;
}
return time;
}
//0
class Truck {
int time;
int weight;
public Truck(int x, int y) {
this.time = x;
this.weight = y;
}
}풀이
전반적인 풀이는 세개의 큐(다리를 통과한 큐, 다리 위 큐, 대기중인 큐)를 생성하고 하나의 큐에서 다른 큐로 옮겨가면서 모든 트럭이 다리를 다 통과 할때 까지 반복문을 돌리고 마지막으로 걸린 시간을 반환한다.
- 트럭 class를 정의해 주고 생성자로 시간과 무게를 받는다.
- 세개의 큐를 생성한다. 다리 위에 있는 트럭을 담을 큐, 다리를 지난 트럭 큐, 대기중인 트럭 큐. 그리고 대기 중인 큐에 파라미터로 받은 다리 길이와 무게를 반복문을 돌면서 넣어준다.
- 현재 다리 위 트럭의 무게(cur_total_weight)를 0 설정. complete 큐의 사이즈가 truck 개수와 같아질때 까지 반복문 수행
- 다리위에 트럭이 있고 맨 앞에 있는 트럭의 시간이 0일 경우 cur_total_weight에서 해당 트럭의 무게를 빼주고 complete 큐에 넣어준다.
- 대기 중인 트럭이 다리 위로 올라갈때 문제 에서 제시간 조건을 만족하는지 확인 한다.
- 다리 위에 있는 트럭들의 시간을 1씩 감소 시킨다.
