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

난이도 : Lv 2

분류 : 스택 / 큐

 

문제

 

프로그래머스

 

코드

 

import Foundation


func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
    var bridge = Array(repeating: 0, count: bridge_length)
    var trucks = truck_weights
    var time = 0
    var bridgeWeight = 0

    
    while !bridge.isEmpty {
        time += 1
        // 한 번 처리 마다 1초씩 증가한다.
        
        bridgeWeight -= bridge.removeFirst()
        // 지나간 트럭의 무게를 다리가 감당할 무게에서 빼준다.

        if let t = trucks.first {
            if t + bridgeWeight <= weight {
            // 대기중인 트럭의 무게와 현재 다리가 감당할 무게를 더해 다리가 감당할 수 있는 무게와 비교한다.
                
                let tmp = trucks.removeFirst()
                // 대기 트럭이 다리를 건널 준비를 한다.
                
                bridge.append(t)
                // 다리에 진입한다.
                
                bridgeWeight += tmp
                // 다리에 진입했으므로 다리가 감당할 무게에 더해준다.
                
            } else {
                bridge.append(0)
                // 다리가 감당할 수 없는 무게라면 트럭을 보내지 않는다.
            }
        }
    }
    return time
}

풀이

1. 다리가 감당할 수 있는 무게 만큼의 트럭이 지나갈 수 있다.

2. 다리의 길이 만큼의 배열을 만들어서 트럭을 지나가게 한다.

3. 길이 3, 하중 10 의 다리를 무게 [7, 3, 2, 5] 트럭들이 건너는 과정은 아래와 같다.

다리	다리에 가하는 무게	남은 트럭들	시간
[ 0, 0, 0 ]	0	[ 7, 3, 2, 5 ]	0
[ 0, 0, 7 ]	7	[ 3, 2, 5 ]	1
[ 0, 7, 3 ]	10	[ 2, 5 ]	2
[ 7, 3, 0 ]	10	[ 2, 5 ]	3
[ 3, 0, 2 ]	5	[ 5 ]	4
[ 0, 2, 5 ]	7	[ ]	5
[ 2, 5, 0 ]	7	[ ]	6
[ 5, 0, 0 ]	5	[ ]	7
[ 0, 0, 0 ]	0	[ ]	8

 

P.S

생각보다 고민을 많이 했으나 결국 다른 사람의 풀이를 보게 만든 문제였다.

링크드 리스트를 이용해 큐를 구현해서 사용할까 하다가. 오버헤드가 발생하지만 removeFirst() 를 사용해서 해결했다.

링크드 리스트를 정리하면서 다시 풀어봐야겠다.