[프로그래머스] 다리를 지나는 트럭 with Swift, Python

• 연습문제
• 다리를 지나는 트럭
• Level 2

#자료구조 #큐

 

문제

• 다리에는 트럭이 최대 bridge_length 수만큼 올라갈 수 있고 (다리의 길이이기도 함)
• 다리는 weight 이하의 무게를 견딜 수 있음. 
• 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 구하기
• 트럭은 1초에 1만큼 움직임 

 

• bridge_length는 1 이상 10,000 이하.
• weight는 1 이상 10,000 이하.
• truck_weights의 길이(트럭 개수)는 1 이상 10,000 이하.
• 모든 트럭의 무게는 1 이상 weight 이하.

 

예. 길이 2, 10kg 무게를 견딤

트럭 : [7, 4, 5, 6]kg

 

0초 

1초 7_

2초 _7

3초 4_

4초 54

5초 _5

6초 6_

7초 _6

8초 

 

Idea

• 다리 위의 상태를 나타내는 큐 만들기. 이때, 다리의 길이만큼 0으로 초기화해주기

 

• 큐에 트럭이 있는 동안 
• 1초씩 증가
• 맨 앞(맨 오른쪽) 값을 pop 하고
• 아직 가야 할 트럭이 있다면

• 현재 다리 위의 무게와 새로 출발할 트럭의 합이 허용 가능하면
• 다리 위에 올리고(트럭 리스트에서 pop)
• 그렇지 않다면 0 추가

 

 

Code

Swift

• 다리 위에 올라갈 무게가 기준을 초과할 때 0을 추가한다는 건 생각했지만 처음부터 다리 길이만큼의 배열을 만들어야겠다는 부분을 떠올리지 못했다.
• 그래서 고민할 것이 많은 코드가 되었었는데 결국 이전 풀이를 참고해서 다리 길이만큼의 배열을 만들어두면 된다는 것을 확인하고 그 부분을 고치니 모든 것이 해결되었다. ㅜㅜ
• 한참 오래전에 풀었을 때는 어떻게 풀어야 할지 더 감을 못 잡았었는데 그래도 이번엔 거의 다 왔다!

import Foundation

func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
    
    var totalTime = 0
    var bridge = Array(repeating: 0, count: bridge_length)
    var totalWeight = 0
    var trucks = truck_weights
    
    while !bridge.isEmpty {
        
        totalTime += 1
        
        let arrived = bridge.removeFirst()
        totalWeight -= arrived
        
        if !trucks.isEmpty {
            if totalWeight + trucks[0] <= weight {
                let next = trucks.removeFirst()
                bridge.append(next)
                totalWeight += next
            } else {
                bridge.append(0)
            }
        }
    }
    
    return totalTime
}

 

Python

• 예전에 풀었을 때 참고했던 코드
• 알고리즘 풀이 프로그래머스 : 다리를 지나는 트럭, Level2(스택/큐)

def solution(bridge_length, weight, truck_weights):
    answer = 0
    
    queue = [0 for _ in range(bridge_length)]
    while queue:
        answer += 1
        queue.pop(0)
        if truck_weights:
            if sum(queue) + truck_weights[0] <= weight:
                queue.append(truck_weights.pop(0))
            else:
                queue.append(0)
    
    return answer