[프로그래머스] (LV2) 다리를 지나는 트럭

다리를 지나는 트럭

JavaScript, Python

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.\
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

bridge_length	weight	truck_weights	return
2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

출처

※ 공지 - 2020년 4월 06일 테스트케이스가 추가되었습니다.

풀이

---

javascript

function solution(bridge_length, weight, truck_weights) {
    var answer = 0;
    var on_bridge_weight = 0;
    var on_bridge = [];
    while(truck_weights.length || on_bridge.length){
        
        on_bridge.forEach((truck)=>{
            truck[0]--;
        })
        
        if(on_bridge.length && on_bridge[0][0] === 0){
            on_bridge_weight -= on_bridge.shift()[1];
        }
        
        if(on_bridge_weight + truck_weights[0] <= weight){
            var cur_truck = truck_weights.shift()
            on_bridge.push([bridge_length,cur_truck]);
            on_bridge_weight += cur_truck;
        }
    
        answer++;
    }
    
    return answer;
}

python

def solution(bridge_length, weight, truck_weights):
    b = []
    answer = 0
    while len(truck_weights) or len(b):
        answer += 1
        returns = -1
        for i in range(len(b)):
            if b[i][1] == 1:        
                returns = i
            else:
                b[i][1] -= 1
        
        for i in range(returns+1):
            b.pop(0)
        
        count = sum(map(lambda a:a[0],b))
        
        if len(truck_weights) and count + truck_weights[0] <= weight:
            t = truck_weights.pop(0)
            b.append([t,bridge_length])
            count += t

    return answer

python 간략화

def solution(bridge_length, weight, truck_weights):
    q = [0] * bridge_length
    q_sum = 0
    answer = 0
    while q:
        answer += 1
        q_sum -= q.pop(0)
        if truck_weights:
            if q_sum + truck_weights[0] <= weight:
                t_pop = truck_weights.pop(0)
                q.append(t_pop)
                q_sum += t_pop
            else:
                q.append(0)
    return answer

설명

---

큐와 스택의 심화 문제다.
다리(bridge)의 상태를 큐로 표현하여 풀었다.

문제에서 주어진 트럭의 무게 배열을 중심으로 while문을 이용한 풀이는 O(N³)를 보였다.
그러나 인터넷에는 bridge를 중심으로 풀이한 O(N²) 풀이가 있다.

python의 pop(0)은 O(N)을 가지는 것을 감안해도 매우 효율적인 방법이다.
당연히 풀이 코드 또한 훨씬 간결하다.

(인터넷의 풀이에는 sum을 while문 안에서 사용하여 효율성이 조금 떨어졌는데,
sum 변수를 활용하여 이를 개선시켰다.)

앞으로도 문제에서 주어진 변수에만 집중하는 버릇을 경계해야겠다.