[코딩테스트] 트럭 (Queue)

문제

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

입력

입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.

출력

출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

예제 입력 1

4 2 10
7 4 5 6

예제 출력 1

8

예제 입력 2

1 100 100
10

예제 출력 2

101

예제 입력 3

10 100 100
10 10 10 10 10 10 10 10 10 10

예제 출력 3

110

생각

• 트럭들이 다리를 순서대로 지나가고, 다리에 올라갈 수 있는 트럭의 수 제한(w)이 있으니, 다리를 큐로 선언하였다

• 다리의 길이만큼 큐를 0으로 채웠다. 여기서 숫자는 무게를 의미하고, 0은 다리위의 공간에 트럭이 없음을 의미한다

• 시간을 1씩 증가하면서 다리의 맨 앞에서 트럭을 꺼내 현재 다리의 무게를 갱신하고, 새로운 트럭의 무게와의 합이 L 이하이면 다리에 추가하고, 그렇지 않으면 0을 추가

• 🌟 모든 트럭이 다리에 진입하는 순간까지 반복하고, 마지막 트럭이 다리에 완전히 올라온 뒤 다리 길이만큼의 시간을 더해주어 마지막 트럭이 빠져나오는 시간을 구하였다 🌟

• 예시
  

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Truck {

    public int getMinTime(int n, int w, int L, int[] trucks) {
        Queue<Integer> bridge = new LinkedList<>();
        int currentWeight = 0;
        int time = 0;
        int index = 0;

        while (bridge.size() < w) {
            bridge.add(0);
        }

        while (index < n) {
            time++;
            currentWeight -= bridge.poll();

            if (currentWeight + trucks[index] <= L) {
                bridge.add(trucks[index]);
                currentWeight += trucks[index];
                index++;
            } else {
                bridge.add(0);
            }
        }

        return time + w;

    }

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

        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int w = Integer.parseInt(firstLine[1]);
        int L = Integer.parseInt(firstLine[2]);

        String[] secondLine = br.readLine().split(" ");
        int[] trucks = new int[n];
        for (int i = 0; i < n; i++) {
            trucks[i] = Integer.parseInt(secondLine[i]);
        }

        System.out.println(T.getMinTime(n, w, L, trucks));
    }
}

생각

• 처음에 마지막 트럭이 다리를 빠져나오는 시간이 아닌, 다리위에 올라오는 시간으로 구해서 예제 입력에 대한 답이 맞지 않았었다.
• 문제를 제대로 풀어놓고 마지막에 놓치지 않도록, 꼼꼼하게 살펴봐야겠다고 생각했다!!

---

문제 출처