[고득점 Kit(스택/큐)] 다리를 지나는 트럭 (Swift, Python)

 

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

 

풀이

 입력으로 주어진 트럭들을 순서대로 bridgeQueue에 append한다. 현재 다리에 있는 모든 트럭의 무게를 합한 값에 지금 다리로 진입해야 하는 트럭의 무게가 합해졌을 때 제한 무게를 넘지 않는지 체크한다. 만약 넘지 않을 경우에는 다리에 트럭을 진입시키는데 이때 (트럭의 무게, 다리에 진입한 시간)의 형태로 bridgeQueue에 넣어줬다. 

 만약 무게 제한을 넘어설 경우에는 bridgeQueue에서 가장 먼저 들어온 트럭을 pop해준다. 이때, 시간을 잘 체크해야 하는데 다리를 빠져나가는 트럭의 시간과 현재 시간 중 더 큰 값(나중 시간)으로 설정해줘야한다. 

 

 입력으로 주어진 트럭을 모두 bridgeQueue에 넣었을 경우 반복문을 종료시키고 제일 마지막에 다리로 진입한 트럭의 다리를 건너는 시간(다리로 진입한 시간 + 다리의 길이)을 리턴해주면 된다.

 

코드

[Swift]

import Foundation
 
typealias truckTuple = (truckWeight: Int, time: Int)
 
func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
    var time: Int = 1 // 현재 시간
    
    var bridgeQueue: [truckTuple] = [] // 다리에 있는 트럭들을 담기 위한 큐
    var nowWeight: Int = 0 // 현재 다리 위에 있는 트럭들의 무게의 합
    
    var idx: Int = 0 // 입력으로 주어진 트럭 배열의 인덱스
    var truckWeight: Int = 0 // 다리로 진입시키려는 트럭의 무게
    
    while idx < truck_weights.count {
        truckWeight = truck_weights[idx] // idx번의 truck을 진입시키기 위해 값을 가져온다.
        
        // idx번의 트럭을 진입시켰을 때 무게 제한을 넘기지 않을 경우
        if nowWeight + truckWeight <= weight {
            bridgeQueue.append((truckWeight, time)) // 다리에 truck을 진입시킨다. (트럭의 무게, 다리 진입 시간)
            nowWeight += truckWeight
            time += 1 // 다음 truck이 진입할 수 있는 시간
            idx += 1
        } else { // 무게 제한을 넘겼을 경우에는 현재 다리에 있는 truck을 탈출시킨다.
            let completeTruck: truckTuple = bridgeQueue.removeFirst()
            nowWeight -= completeTruck.truckWeight
            
            // 시간의 경우 위에서 구한 다음 truck이 진입할 수 있는 시간과
            // 다리에서 탈출시키는 truck의 다리를 건너는 데 걸린 시간 중 더 큰 값으로 설정해야 한다.
            time = max(time, completeTruck.time + bridge_length)
        }
    }
    
    guard let lastTruck = bridgeQueue.popLast() else { return 0 }
    
    return lastTruck.time + bridge_length
}
 

 

[Python]

from collections import deque
 
 
def solution(bridge_length, weight, truck_weights):
    time = 1 # 현재 시간 
 
    bridgeQueue = deque() # 다리에 있는 트럭들을 담기 위한 큐 
    nowWeight = 0 # 현재 다리 위에 있는 트럭들의 무게의 합 
 
    idx = 0 # 입력으로 주어진 트럭 배열의 인덱스
    truckWeight = 0 # 다리로 진입시키려는 트럭의 무게 
 
    while idx < len(truck_weights):
        truckWeight = truck_weights[idx] # idx번의 truck을 진입시키기 위해 값을 가져온다.
 
        # idx번의 트럭을 진입시켰을 때 무게 제한을 넘기지 않을 경우 
        if nowWeight + truckWeight <= weight:
            bridgeQueue.append((truckWeight, time)) # 다리에 truck을 진입시킨다. (트럭의 무게, 다리 진입 시간)
            nowWeight += truckWeight 
            time += 1 # 다음 truck이 진입할 수 있는 시간
            idx += 1 
        else: # 무게 제한을 넘겼을 경우에는 현재 다리에 있는 truck을 탈출시킨다. 
            (completeTruckWeight, inTime) = bridgeQueue.popleft()
            nowWeight -= completeTruckWeight 
 
            # 시간의 경우 위에서 구한 다음 truck이 진입할 수 있는 시간과
            # 다리에서 탈출시키는 truck의 다리를 건너는 데 걸린 시간 중 더 큰 값으로 설정해야 한다.
            time = max(time, inTime + bridge_length) 
 
 
    return bridgeQueue.pop()[1] + bridge_length