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

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

✍️ 첫번째 접근

다리에는 트럭이 최대 bridge_length대 올라갈 수 있으므로 배열의 크기를 bridge_length로 설정하여 문제를 풀었다. bridge_length는 1 이상 10,000 이하이지만 이 배열을 실제로 트럭이 움직이는 것처럼 하기 위해서 배열을 하나씩 움직이는 과정이 시간적 비용이 매우 클 거 같아 아래와 같이 구현하였다.

• 고차함수의 사용을 줄이기 위해 같은 로직인 함수를 정의하였다.
• 배열에 모든 원소를 한칸씩 앞으로 당기는 로직을 for문을 통해서 했는데 비효율적이라고 판단하여 removeFirst, append로 대체하였다.
  

하지만, 시간 초과가 발생하였다.

import Foundation

func zeroCount(_ arr: [Int]) -> Int {
    var cnt: Int = 0
    for i in arr {
        if i == 0 {
            cnt += 1
        }
    }
    return cnt
}

func sum(_ arr: [Int]) -> Int {
    var sum: Int = 0
    for i in arr {
        sum += i
    }
    return sum
}

func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
    var answer: Int = 0
    
    var trucks: [Int] = truck_weights
    var arr: [Int] = Array(repeating: 0, count: bridge_length)
    while(!trucks.isEmpty) {
        if sum(arr) + trucks.first! <= weight {
            arr.removeFirst()
            arr.append(0)
            arr[arr.count-1] = trucks.first!
            trucks.removeFirst()
            answer += 1
        }
        else {
            arr.removeFirst()
            arr.append(0)
            answer += 1
            if sum(arr) + trucks.first! <= weight {
                arr[arr.count-1] = trucks.first!
                trucks.removeFirst()                
            }
        }
    }
    if(zeroCount(arr) != arr.count) {
        answer += arr.count
    }
    
    return answer
}

✍️ 두번째 접근

처음 배열을 초기화할 때 크기를 bridge_length로 하였기 때문에 틀렸다고 판단했다.
직관적으로 문제를 곧이곧대로 구현하여 해결하지 말고 즉, 배열을 하나만 쓰지 말고 배열을 2개를 정의하였다. 다리를 건너는 트럭을 저장하는 배열 1개, 각 트럭에 대한 시간을 저장하는 배열 1개 이렇게 말이다.
각 트럭에 대한 시간을 저장하는 배열의 첫번째 원소가 bridge_length와 같아지면 두 배열의 첫번째 원소를 삭제하는 로직으로 해결하였다.
예전에도 이런 경험이 있었지만, 문제를 곧이곧대로 보지 말고 덩어리로 분리해서 봐야함을 인지해야겠다.

import Foundation

func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
    var answer: Int = 0
    var trucks: [Int] = truck_weights
    var isMoving: [Int] = []
    var times: [Int] = []
    // 첫번째 대기 트럭
    isMoving.append(trucks.first!)
    times.append(1)
    trucks.removeFirst()
    answer += 1
    
    while(!isMoving.isEmpty || !times.isEmpty) {
        if times.first! >= bridge_length {
            isMoving.removeFirst()
            times.removeFirst()
            answer += 1
        }
        if !trucks.isEmpty && isMoving.reduce(0,+) + trucks.first! <= weight {
            isMoving.append(trucks.first!)
            trucks.removeFirst()
            times = times.map { $0 + 1 }
            times.append(1)
        }
        else {
            // times[0] = times[0] + 1
            times = times.map { $0 + 1 }
            answer += 1
        }
    }
    answer -= 1
    return answer
}