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

<문제>

---

<전략짜기>

대기하고 있는 트럭에 대해서 순서대로 bridge에 진입을 시도해야 하는데, 그 조건이 지금 내가(대기하는 첫번째 트럭) bridge에 올라가도 무게를 견딜 수 있니? 를 만족해야 한다. 만약 견딜 수 있다면 새로운 트럭을 진입시키고, 견딜 수 없다면 빈칸을 한칸 보낸다. (다리가 가득 찼을 경우 가장 앞에 있는 트럭을 탈출시키기 위해 얼마만큼 이동했는지 확인하기 위해 빈칸을 보내야 한다.. 이렇게 빈칸을 보내주지 않고 얼마만큼 이동했는지 위치를 알기 위해서는 트럭의 무게와 현재위치를 Property로 가지는 struct를 생성해야 할것같다..😭) 동시에 이때 진행시간을 1초씩 더해줘야 한다. 이 과정을 대기하는 트럭이 없어질때까지 반복시켜준다!

 

<코드>

import Foundation

func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
    var bridge: [Int] = []
    var curWeight = weight
    var time: Int = bridge_length

    for truck in truck_weights {
        while true {
            if bridge.count == bridge_length {
                if let firstTruck = bridge.first {
                    curWeight += firstTruck
                    bridge.removeFirst()
                }
            } else {
                if curWeight < truck {
                    bridge.append(0)
                    time += 1
                } else {
                    bridge.append(truck)
                    time += 1
                    curWeight -= truck
                    break
                }
            }
        }
    }

    return time
}

 

<Lesson Learned>

제출했는데 오답.. 응?? 무슨일이지..?? 하면서 곰곰히 보는데.. 전략짠대로 알고리즘을 구현했더니 제일 '마지막'에 들어간 트럭이 말썽이였다.. 알고리즘대로면 마지막 트럭이 진입하면 (대기하는 트럭이 없으면) 이동을 완료했다고 간주하게 된다. 그러나.. 마지막 트럭은 bridge에 진입했을 뿐 탈출은 하지 못했다는거.. ㅋㅋㅋ(여기에 시간 초기값이 당연히 0이였음 😭) 그래서.. 그냥 루프 이후에 bridge가 빌때까지 하나씩 지워주면서 시간을 더해버릴까? 하다가.. 생각해보니 time의 초기값을 0이아닌 다리의 길이만큼으로 설정하면, 마지막에 트럭이 이동하는 시간만큼 더해질 수 있는 동시에 불필요한 루프(다리 길이만큼)를 돌지 않아도 된다!! 그리고.. 그와중에 또 하나 다른사람의 풀이를 참고해서 문제 풀때 참고할만한 기법을 배워서 발췌해왔다. 

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

    while bridge.isEmpty == false {
        // 1초마다 다리위의 트럭 또는 빈공간은 움직임
        w -= bridge.removeFirst()
        sec += 1

        // 다리에 빈 공간 있으면
        if bridge.count < bridge_length {
            // 다리에 진입 예정인 트럭을 포함한 무게와 다리가 견딜 수 있는 무게를 비교해서
            // 견딜 수 있으면 트럭 진입 시킨다.
            if let t = trucks.first {
                if t + w <= weight  {
                    w += trucks.removeFirst() // 트럭 진입
                    bridge.append(t) // 트럭 진입 완료
                } else {
                    // 견딜 수 업으면 트럭 대기하고 빈공간만 보낸다.
                    bridge.append(0)
                }
            }
        }
    }

    return sec
}

전체적인 알고리즘의 논리는 거의 동일한데, 이 분은 초기에 다리의 길이를 입력받은 길이만큼 고정적으로 정해놓고 시작했다! 나는 솔직히 이런 생각은 아예 못했고, 하나씩 넣고 빼고 할 생각밖에 못했음.. 😂 이렇게 생각하고 하니 제일 앞에 있는 것(트럭 or 빈칸)을 무조건 빼고 시작해도 되는, 그리고 bridge가 비어있을 리가 없다는 강력한 가정이 생겨서, 훨씬 명확하고 간단하게 구현이 가능한 것 같다. 아무튼 이번에 여기서 배운건 배열을 시작부터 채울 필요가 없고, 미리 의미없는 값으로 설정해놓고 시작하는 것도 하나의 방법이라는 것이다~!!👍

 

 

 

출저 : 프로그래머스 다리를 지나는 트럭