백준 - 트럭(13335)

오늘 풀어본 문제는 ⭐트럭 이란 문제다.

1. 문제요약

• n개의 트럭이 다리를 건너려고 한다.
• 1초에 1씩 움직인다는 가정. 다리에 올라간 트럭 무게 총 합 <= L
• 트럭길이는 모두 1로 돋일
• 땅과 걸쳐져있는 트럭은 무게에 합하지 않음(자리 차지만)
• 모든 트럭이 건너는 최단 시간 구하기

2. 입력

• n개의 트럭 무게
• 다리길이 w
• 다리하중 L

3. 알고리즘 - 그리디

• 다리길이만큼 어레이리스트를 만듦
• 큐에 트럭 무게, 끝을 나타내는 boolean 변수 담은 클래스 넣음
• 큐에 w만큼 0을 넣음. (빈 칸이라는 의미)

4. 내 코드

import java.io.*;
import java.util.*;

class Info {
    int weight;
    boolean end;

    public Info(int weight, boolean end){
        this.weight = weight;
        this.end = end;
    }
}

public class Main {
    static Queue<Info> bridge;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n,w,l;

        n = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());

        bridge = new ArrayDeque<>();
        Queue<Info> truck = new ArrayDeque<>();

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            int weight = Integer.parseInt(st.nextToken());
            boolean end = i==n-1;
            truck.add(new Info(weight, end));
        }

        for(int i=0; i<w; i++){
            bridge.add(new Info(0, false));
        }

        Info nowTruck = bridge.peek();
        int time = 0;
        while (!nowTruck.end) {
            time++;
            bridge.poll();
            int nowBridgeWeight = calculateBridgeSum();
            if(!truck.isEmpty() && truck.peek().weight  + nowBridgeWeight <= l)
                bridge.add(truck.poll());
            else
                bridge.add(new Info(0,false));
            nowTruck = bridge.peek();
        }

        System.out.println(time+1);
    }

    static int calculateBridgeSum() {
        int sum = 0;
        for(Info truck : bridge) {
            sum += truck.weight;
        }
        return sum;
    }

}

5. 알게 된 점

문제를 풀면서 궁금했던 점이 있다.

바로 두 가지 변수가 들어있는 클래스에 대한 List를 Stream으로 간편하게 계산할 수 있을까? 였다.

되긴 한다!!

            int nowBridgeWeight = bridge.stream()
                    .mapToInt(info -> info.weight)
                    .sum();

그러나 스트림으로 사용할 경우, for문보다 많이 느린 것을 확인할 수 있었다.

스트림은 다음과 같은 과정을 거친다.

Collection → Spliterator → Pipeline → Terminal Operation

그렇기에 단순 더하기만 하면 되는 기존 코드보다 느려질 수 밖에 없다.
스트림은 대용량 환경에서만 유리하다는 것!!