다리 길이만큼의 길이를 가진 배열(모든 요소는 0)을 만든 뒤 트럭을 올릴때마다 추가한다.
모든 대기열의 트럭이 다 올라가는 순간, 마지막에 올라간 트럭이 트럭을 벗어나는 시간을 계산할 수 있으므로 트럭이 다 올라가는 순간 작업은 끝난다.
필요한 작업 :
다리에 올라가는 트럭을 따로 관리할 배열
다리를 지날 경우, 다리에 올라간 트럭 배열에 해당 트럭이 있다면 제외시키는 함수
생각해 낸 아이디어 :
1. 1초가 지날때마다 다리의 맨 끝은 제거되고 맨 앞은 0을 추가하는 작업이 필요하다.
2. 트럭에 올라간 배열을 따로 관리해야 한다. 다리길이와 같은 배열으로 관리하게 되면 다리 길이가 길어질 때 엄청나게 긴 작업시간이 소요된다. (자료구조)
3. 모든 대기열의 트럭이 올라갔을 때 남은 소요시간은 다음과 같이 계산한다. '다리 전체 길이 - 마지막 트럭이 위치'
import Foundation
func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
// 트럭이 한 대면 다리 길이를 이용하여 계산 가능
guard truck_weights.count != 1 else {
return bridge_length + 1
}
// 한 개의 배열에서 제거한 값이 다른 배열에 있다면 같이 삭제하는 함수.
// 1초가 지날 때 마다 다리를 완전 통과하는 트럭이 다리에 올라간 트럭 배열에도 있으면 지워준다.
func removeLast2(from arr: inout[Int], with arr2: inout[Int]) {
if let inx = arr2.firstIndex(of: arr.removeLast()) {
arr2.remove(at: inx)
}
}
// 한 개의 배열에서 제거한 값을 다른 두 배열에 반영하는 함수.
// 반영해야 할 배열 : 다리의 현황을 표현하는 배열, 다리에 올라간 트럭 배열.
func removeFirst2(from arr: inout[Int], with arr2: inout[Int], value: Int) {
arr[0] = value
arr2.append(value)
}
var truck_weights = truck_weights
var trucksInBridge = [Int]() // 다리에 올라와 있는 트럭의 무게만 저장하는 배열
var bridgeCamera = Array(repeating: 0, count: bridge_length) // 다리의 현황을 나타내는 배열
var results = 0 // 소요 시간
while !truck_weights.isEmpty {
// 1초 진행될 때 마다 bridgeCamera의 마지막을 제거하고 맨 앞에 0을 추가한다.
results += 1
removeLast2(from: &bridgeCamera, with: &trucksInBridge)
bridgeCamera.insert(0, at: 0)
while !truck_weights.isEmpty {
// 다리에 있는 트럭들의 무게, 출발 예정의 트럭 무게 합이 weight보다 작거나 같으면 계속 추가하면서 한칸씩 이동시킴.
if trucksInBridge.reduce(0, {$0+$1}) + truck_weights.first! <= weight {
results += 1
removeFirst2(from: &bridgeCamera, with: &trucksInBridge, value: truck_weights.removeFirst())
removeLast2(from: &bridgeCamera, with: &trucksInBridge)
bridgeCamera.insert(0, at: 0)
} else {
break
}
}
// 더 이상 이동시킬 트럭이 없을 경우 다리의 현황을 이용하여 한번에 계산
if truck_weights.isEmpty {
results +=
(bridgeCamera.count - (bridgeCamera.firstIndex(where: {$0 != 0}) ?? 0))
break
}
}
return results
}
약 3~4시간이 걸렸다.
최대한 시간을 적게 활용하기 위해 다리에 올라가는 트럭 만 따로 관리하는 배열을 만들었다.
트럭의 합을 Int 변수로 해도 되었을까 싶지만, 트럭이 다리에서 빠져나올 때 정확한 값을 제외할 수 없을 것이므로 배열을 사용하는 방법으로 포스팅한다.