[알고리즘] 다리를 지나는 트럭

백상휘·2020년 8월 31일
0

알고리즘

목록 보기
2/4

해당 문제는 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/42583)에 출제된 문제를 채점한 결과를 토대로 작성하였습니다.

다리 길이만큼의 길이를 가진 배열(모든 요소는 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 변수로 해도 되었을까 싶지만, 트럭이 다리에서 빠져나올 때 정확한 값을 제외할 수 없을 것이므로 배열을 사용하는 방법으로 포스팅한다.

profile
plug-compatible programming unit

0개의 댓글