다리를 지나는 트럭 Lv2

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

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스

분류: Lv2, 스택/큐

---

순서대로 서있는 트럭들이 다리를 안전하게 건너려면 총 얼마가 걸리는가 하는 문제입니다.

2개의 큐를 사용해서 해결하였습니다.

먼저 다리 위에 있는 트럭들을 담을 onBridge Queue와

트럭들이 들어온 시간을 담는 times Queue를 만들었습니다.

전체 시간과 시간 큐의 시간을 비교하면 해당 트럭이 얼마나 있었는지 확인할 수 있습니다.

 

동시에 2대 이상의 트럭이 빠져나갈 수는 없기 때문에 큐의 첫번째를 확인해서 통과할 시간이 되었으면 큐에서 제거해주면 되고,

다리에 트럭이 있는 만큼 버틸 수 있는 weight을 확인해주면서 큐에 담으면 됩니다.

이렇게 다리 위의 트럭과 대기하고 있는 트럭이 없을 때 최종 경과시간이 됩니다.

// 스택/큐
// 다리를 지나는 트럭
// https://programmers.co.kr/learn/courses/30/lessons/42583?language=swift

import Foundation

func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
    
    var onBridge: [Int] = []
    var times: [Int] = []
    var total = 0
    var w = weight
    
    var waits = truck_weights
    
    
    
    while !waits.isEmpty || !onBridge.isEmpty {
        total += 1
        
        // 큐의 첫번째가 시간이 다 됐으면 pop
        if let time = times.first, total - time == bridge_length {
            times.removeFirst()
            w += onBridge.removeFirst()
        }
        
        // 트럭이 들어갈 수 있으면
        if let truck = waits.first, truck <= w {
            w -= waits.removeFirst()
            onBridge.append(truck)
            times.append(total)
        }
    }
    
    return total
}

 

회고

간단한 문제인데 생각보다 큐에 익숙하지 않아 애를 많이 먹었다... 

일정한 속도로 움직이기 때문에 초마다 확인해주면 되는데, 각 트럭이 빠져나가는데 걸리는 시간을 계산하려고 하다보니 생각이 많이 꼬였던 것 같다. 아예 객체를 따로 만들어서 각 객체의 경과 시간이 지나면 제거해주는 방식으로 해결해도 될 듯 하다.

자꾸 각 문제를 하나 하나 독립적으로 생각하려고 하는데, 문제를 어떤 자료구조와 알고리즘으로 접근해야 할 지 먼저 생각해서 유형별로 분류하는 연습을 많이 해야겠다.