8. 다리를 지나는 트럭

https://programmers.co.kr/learn/courses/30/lessons/42583

문제에서 제시된 조건을 프로그래밍 언어로 그대로 옮겨주면 되는데 구현이 어렵지 않습니다. 
다리만큼 배열을 만들고 거기에 트럭을 하나씩 올리면서 무게 체크를 하면서 한칸씩 옮겨주면 됩니다. 
다만 약간의 최적화를 해주면 더욱 좋은 결과가 나오기 때문에 시간 제한에 유의하셔야 합니다. 

코딩테스트 연습 - 다리를 지나는 트럭

파이썬

def solution(bridge_length, weight, truck_weights):
    bridge = [0] * bridge_length
    arrival, time = 0, 0
    truck_num = len(truck_weights)
    while arrival != truck_num:
        time += 1
        if bridge.pop(0) > 0:
            arrival += 1
        if truck_weights and sum(bridge) + truck_weights[0] <= weight:
            bridge.append(truck_weights.pop(0))
        else:
            bridge.append(0)
    return time

'''
테스트 1 〉	통과 (13.32ms, 10.6MB)
테스트 2 〉	통과 (1652.51ms, 10.8MB)
테스트 3 〉	통과 (0.05ms, 10.7MB)
테스트 4 〉	통과 (366.92ms, 10.8MB)
테스트 5 〉	통과 (9952.94ms, 10.8MB)
'''

통과될 줄 모르고 돌렸는데 통과가 되어 버린 케이스... (두 가지 함정이 있거든요 ㅠ,.ㅠ)
for 문 내의 sum 함수 때문에 많이 느리네요. 좀 수정해 볼까요?

def solution(bridge_length, weight, truck_weights):
    bridge = [0] * bridge_length
    arrival_count, time, sum_weight = 0, 0, 0
    truck_num = len(truck_weights)
    while arrival_count != truck_num:
        time += 1
        arrival = bridge.pop(0)
        if arrival > 0:
            sum_weight -= arrival
            arrival_count += 1
        if truck_weights and sum_weight + truck_weights[0] <= weight:
            new_truck = truck_weights.pop(0)
            bridge.append(new_truck)
            sum_weight += new_truck
        else:
            bridge.append(0)
    return time

'''
테스트 1 〉	통과 (0.82ms, 10.8MB)
테스트 2 〉	통과 (51.73ms, 10.9MB)
테스트 3 〉	통과 (0.05ms, 10.7MB)
테스트 4 〉	통과 (10.64ms, 10.7MB)
테스트 5 〉	통과 (298.25ms, 10.8MB)
'''

리스트에서 pop(0)을 하는 것은 느립니다.
제 블로그에서도 이에 대해서 설명을 한 적이 있습니다. 
https://comdoc.tistory.com/entry/13-%ED%81%90queue-ADT-%ED%8C%8C%EC%9D%B4%EC%8D%ACwith-Python

제대로 큐를 구현하려면,
양 끝에서의 덧붙이기와 꺼내기가 모두 빠르도록 설계된 collections.deque 를 사용해야 합니다. 

from collections import deque


def solution(bridge_length, weight, truck_weights):
    bridge = deque([0] * bridge_length)
    truck_weights = deque(truck_weights)  # 테스트 결과 트럭 대수는 속도에 큰 관계가 없었지만. 일관성을 위해.
    arrival_count, time, sum_weight = 0, 0, 0
    truck_num = len(truck_weights)
    while arrival_count != truck_num:
        time += 1
        arrival = bridge.popleft()
        if arrival > 0:
            sum_weight -= arrival
            arrival_count += 1
        if truck_weights and sum_weight + truck_weights[0] <= weight:
            new_truck = truck_weights.popleft()
            bridge.append(new_truck)
            sum_weight += new_truck
        else:
            bridge.append(0)
    return time

'''
테스트 1 〉	통과 (0.53ms, 10.7MB)
테스트 2 〉	통과 (7.26ms, 10.8MB)
테스트 3 〉	통과 (0.05ms, 10.8MB)
테스트 4 〉	통과 (5.90ms, 10.8MB)
테스트 5 〉	통과 (57.47ms, 10.9MB)
'''

속도 차이가 꽤 많이 납니다. 

자바스크립트

function solution(bridge_length, weight, truck_weights) {
    let bridge = []
    for (let index = 0; index < bridge_length; index++)
        bridge.push(0)
    let arrival_count = 0
    let time = 0
    let sum_weight = 0
    let truck_num = truck_weights.length
    while (arrival_count != truck_num) {
        time++;
        let arrival = bridge.shift();
        if (arrival > 0) {
            sum_weight -= arrival
            arrival_count++
        }
        if (sum_weight + truck_weights[0] <= weight) {
            let new_truck = truck_weights.shift()
            bridge.push(new_truck)
            sum_weight += new_truck
        } else {
            bridge.push(0)
        }
    }
    return time
}

자바

import java.util.LinkedList;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        LinkedList<Integer> bridge = new LinkedList<>();
        for (int i = 0; i < bridge_length; i++) bridge.add(0);
        LinkedList<Integer> trucks = new LinkedList<>();
        for (int each : truck_weights) trucks.add(each);
        int time = 0;
        int arrivalCount = 0;
        int totalWeight = 0;
        int truckNum = trucks.size();
        while (arrivalCount != truckNum) {
            time++;
            var arrival = bridge.poll();
            if (arrival > 0) {
                totalWeight -= arrival;
                arrivalCount++;
            }
            if (trucks.isEmpty()) {
                bridge.add(0);
            } else if (totalWeight + trucks.peek() > weight) {
                bridge.add(0);
            } else {
                int newTruck = trucks.poll();
                bridge.add(newTruck);
                totalWeight += newTruck;
            }
        }
        return time;
    }
}

재미있는 부분이 있습니다.
파이썬의 경우 if a & b 의 경우 a가 false면 b로 넘어가지 않습니다. 시간 낭비라는 거죠. 
자바 같은 경우 고지식하게 b 조건 까지 검사하네요.
파이썬의 경우 if (배열이 안 비었냐?) and (배열.pop()) 에서 에러가 없습니다. 
배열이 비었으면 뒤는 실행하지 않기 때문입니다. 
개인적으로 파이썬의 if 문을 더 좋아합니다.
시간도 절약할 수 있고 if 문도 한 번 줄일 수 있기 때문입니다. 
당연히 파이썬의 if문에서는 조건의 순서에 주의해야 합니다. ~!

코틀린

import java.util.*

class Solution {
    fun solution(bridge_length: Int, weight: Int, truck_weights: IntArray): Int {
        val bridge = LinkedList<Int>(Array(bridge_length) {0}.asList())
        val trucks = LinkedList<Int>(truck_weights.asList())
        var time = 0
        var arrivalCount = 0
        var totalWeight = 0
        val truckNum = trucks.size
        while (arrivalCount != truckNum) {
            time++
            val arrival = bridge.poll()
            if (arrival > 0) {
                totalWeight -= arrival
                arrivalCount++
            }
            when {
                trucks.isEmpty() -> bridge.add(0)
                totalWeight + trucks.peek() > weight -> bridge.add(0)
                else -> {
                    val newTruck = trucks.poll()
                    bridge.add(newTruck)
                    totalWeight += newTruck
                }
            }
        }
        return time
    }
}

코틀린도 자바와의 호환성 때문인지 &가 같은 방식으로 작동합니다. 
그래도 when으로 바꾸니 깔끔해 보입니다.

코틀린에서는 링크드 리스트 초기화와 배열 변환을 동시에 할 수 있군요.
코틀린과 인텔리제이는 꽤 똑똑합니다.
혹시나 해서 넣어봤는데 asList 넣으라고 안내 해주네요. 

고언어

func solution(bridgeLength int, weight int, truckWeights []int) (time int) {
	bridge := make([]int, bridgeLength)
	arrival := 0
	truckNum := len(truckWeights)
	totalWeight := 0
	for arrival != truckNum {
		time++
		if bridge[0] > 0 {
			arrival++
			totalWeight -= bridge[0]
		}
		bridge = append(bridge[1:], 0)
		if len(truckWeights) > 0 && totalWeight+truckWeights[0] <= weight {
			bridge[bridgeLength-1] = truckWeights[0]
			totalWeight += truckWeights[0]
			truckWeights = truckWeights[1:]
		}
	}
	return
}

C#

using System.Collections.Generic;

public class Solution
{
    public int solution(int bridge_length, int weight, int[] truck_weights)
    {
        Queue<int> bridge = new Queue<int>(new int[bridge_length]);
        Queue<int> trucks = new Queue<int>(truck_weights);
        int time = 0;
        int arrivalCount = 0;
        int truckNum = truck_weights.Length;
        int totalWeight = 0;
        while (arrivalCount != truckNum)
        {
            time++;
            var arrival = bridge.Dequeue();
            if (arrival > 0)
            {
                totalWeight -= arrival;
                arrivalCount++;
            }
            if (trucks.Count == 0)
                bridge.Enqueue(0);
            else if (totalWeight + trucks.Peek() > weight)
                bridge.Enqueue(0);
            else
            {
                int newTruck = trucks.Dequeue();
                bridge.Enqueue(newTruck);
                totalWeight += newTruck;
            }
        }
        return time;
    }
}

C# 에서도 깔끔하게 인라인으로 초기화, 변환이 동시에 됩니다.
자바에선 인라인으로 깔끔하게 안될까요? 자바 나빠요 ㅠ,.ㅠ
(제가 자바 만년 초보라... 잘 몰라서... 근데... 모르면 자바탓 아닙니까 ^^?)