[JAVA]백준 13335 트럭 Deque, queue

 📚 문제  

https://www.acmicpc.net/problem/13335

13335번: 트럭

🔍 아이디어  

처음에 보고는 우선수위 큐를 이용해서 푸는 문제풀이가 생각났다. 근데 어차피 먼저 들어가는 게 먼저 나오니까 그냥 큐로 풀이했다

 

트럭이 다리에 입장한다면 해당 트럭의 무게와 다음 차례 트럭 무게의 합에 따라 다음 트럭이 입장할 수 있는지가 정해진다.

그리고 한 타임에는 하나의 트럭만 다리에 입장할 수 있다.

 

트럭은 큐에서 빼는 경우는 두 가지 경우가 있다.

1. 트럭이 입장하려고 하는 시점에 큐에 만약 해당 시간에는 없어야 할 트럭이 있다면 뺀다. 

2. 현재 다리위의 하중에 다음 트럭이 들어왔을 때 최대하중을 넘어버린다면 큐에 있는 트럭을 하나 뺀다.

트럭을 뺀 후에는 현재 다리 위의 트럭 하중에서 뺀 트럭을 빼고, 시간을 트럭이 나오는 시점으로 업데이트한다.

이 과정을 현재 트럭이 다리에 들어갈 수 있을 때까지 반복한 후에 현재 트럭을 넣는다.

트럭을 넣는 시점에는 {현재 시간+다리의 길이}이고 데이터 저장용으로 트럭 무게를 넣는다.

 

이후에 모든 트럭이 다리에 올라간 후에는 가장 마지막에 입장한 트럭의 퇴장시간에 완전히 빠져나오는 시간+1을 해주면 답을 출력할 수 있다. 

 

Deque를 사용한 이유는 가장 마지막에 남은 차의 시간을 출력해야 하는데 큐를 이용하면 모두 뽑아내야 하기 때문에 Deque로 마지막 차의 시간을 출력하도록 하였다. 

 

📝 풀이 

package 백준.Deque;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Boj_13335_트럭 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int busCnt = Integer.parseInt(st.nextToken());//버스 수
        int bridgeLength = Integer.parseInt(st.nextToken());//다리 길이
        int bridgeMaxWeight = Integer.parseInt(st.nextToken());//최대 하중

        int nowTotalWeight = 0; //현재 다리위에 올라왔있는 버스들의 무게의 합
        Deque<int[]> onBridge = new ArrayDeque<>(); //[시간, 무게] 다리위에 올라와있는 버스들
        st = new StringTokenizer(br.readLine());
        int time = 0;
        while (busCnt-- > 0) {
            int weight = Integer.parseInt(st.nextToken()); //이번에 들어갈 버스

            //만약 현재 시간이면 나왔어야 할 차가 있는 경우에는 빼준다.
            //이번에 차가 들어가야하는데 무게가 이미 초과 되었다면 이번 차를 넣을 수 있을때까지 이전에 있던 차를 뺀다.
            while (!onBridge.isEmpty() && (bridgeMaxWeight < weight + nowTotalWeight || onBridge.peek()[0] <= time)) { //가능한 시간까지 뺀다.
                int[] nowCar = onBridge.pollFirst(); //앞의 한 차가 빠져나온다.
                time = nowCar[0]; //가장 마지막 차가 나온시간
                nowTotalWeight -= nowCar[1]; //가장 마지막 차가 나왔으므로 다리에 최대 하중에서 빼준다.
            }

            onBridge.addLast(new int[]{time + bridgeLength, weight}); //해당 차가 나올 시간과, 해당 타의 무게
            nowTotalWeight += weight;//해당 차가 다리위로 올라갔다.
            time++; //한 타임이 지났다(한 타임에는 하나의 차만 보낼 수 있다)
        }
        System.out.println(onBridge.pollLast()[0] + 1); //다리에 있던 차가 모두 빠져나간 순간이기에 1을 더한다.
    }
}