다리를 지나는 트럭

풀고 나니까 time을 1씩 더해서 증가하다 보니 시간 효율성이 떨어진다고 생각한다.

첫 시도가 틀린 이유?

1번 테스트케이스에서 결과가 8이 아니라 10이 나왔는데, 다리 위 트럭의 움직임을 잘못 이해했다.
다리 위 트럭은 나가고 들어오고가 동시에 진행된다. 그러므로 두 트럭 무게의 합이 다리 무게보다 크더라도, 첫 트럭이 나가면서 동시에 두번째 트럭이 들어올 수 있다. 첫 트럭이 나가는걸 기다릴 필요가 없다.

0 7
7 0
0 4
4 5
5 0
0 6
6 0
0 0

큐를 사용한 이유?

들어오고 나가는 순서가 FIFO로 정해졌기 때문에 큐를 사용한다.
c++에서 큐는 스택과 동일하게 push(), pop()으로 저장, 삭제가 가능하지만, Java는 스택, 맵, 리스트, 큐 등 각 컨테이너마다 조금씩 다르다.
현재 코드에서는 offer(), peek(), poll()을 사용하는데, 이 메서드들은 실패시 null을 반환해 예외발생을 방지한다.

또한 큐에는 우선순위큐와 이중큐가 존재한다.

메서드	설명
add(e)	큐의 뒤에 요소 추가 (예외 발생 가능)
offer(e)	큐의 뒤에 요소 추가 (성공 여부 반환)
poll()	큐의 앞 요소 제거 후 반환 (비어 있으면 null)
remove()	큐의 앞 요소 제거 후 반환 (비어 있으면 예외)
peek()	큐의 앞 요소 반환 (제거 안 함, 비어 있으면 null)
element()	큐의 앞 요소 반환 (제거 안 함, 비어 있으면 예외)
isEmpty()	큐가 비었는지 확인
size()	큐의 크기 반환

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int i, j;
        int currentWeight = 0;
        int time = 0;
        Queue <Integer> trucks = new LinkedList<>();
        Queue <Integer> bridge = new LinkedList<>();
        
        //큐 : offer, poll, peek
        for(int truck : truck_weights){
            trucks.offer(truck);
        }
        for(i = 0; i < bridge_length; i++){
            bridge.offer(0);
        }
        
        while(!bridge.isEmpty()){
            time++;
            System.out.println("time : " + time);
            
            if(trucks.isEmpty()){
                //대기 중인 트럭이 더 없음
                bridge.poll();
                
                continue;
            }
            
            if(currentWeight - bridge.peek() + trucks.peek() <= weight){
                //다리 위에 트럭이 더 올라와도 됨
                currentWeight -= bridge.peek();//현재 다리 위에 있는 트럭 한칸씩 이동
                bridge.poll();
                
                bridge.offer(trucks.peek());//대기 중인 트럭 다리에 입장
                currentWeight += trucks.peek();//무게 추가
                trucks.poll();
            }
            else{ // currentWeight - bridge.peek() + trucks.peek() > weight
                //다리 위에 트럭이 더 올라오면 안됨
                currentWeight -= bridge.peek();
                bridge.poll();
                bridge.offer(0);
            }
        }
        answer = time;
        
        return answer;
    }
}
/*
0 7
7 0
0 4
4 5
5 0
0 6
6 0
0 0
*/