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

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

 

 

 문제 설명

 

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

프로그래머스

 

 나의 풀이

 

(트럭의무게, 시간초) 튜플을 이용해서 문제를 해결했다.

큐를 사용했지만 구현에 시간을 많이 써서 구현방식으로 풀이를 한 것 같다.

마지막 cnt에 bridge_length를 더하는 이유는 마지막 트럭을 지나서 break가 된 상태에서 마지막 트럭이 다 도달하기 위해서 걸리는 시간은 bridge_length만큼이기 떄문이다.

 

 

import Foundation

func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
    var q: [(Int, Int)] = []
    var idx = 0
    var sum = 0
    var cnt = 0 
    while true {
        // 인덱스가 트럭의 개수보다 커지면
        if idx == truck_weights.count {
            break
        }
        // 큐가 비어있지 않고 들어온 시간이 다리길이가 된다면 제거
        if let first = q.first, first.1 == bridge_length {
                sum -= first.0
                q.removeFirst()    
        }
        // 현재 큐에 무게를 추가했을때 한계무게보다 작다면 추가
        if sum + truck_weights[idx] <= weight {
            sum += truck_weights[idx]
            q.append((truck_weights[idx], 0))
            idx += 1
        } 
        // 큐 각각 트럭에 시간초를 더해주기.
        q = q.map{ ($0.0, $0.1+1) }
        cnt += 1
    }
    cnt += bridge_length
    
    return cnt
}

 

 

 

 다른 사람의 풀이

 

다리의 개수만큼 0으로 초기화해준 뒤 트럭에 값이 들어오면 append하고 무게제한때문에 들어올 수 없다면 0을 넣어줌으로써 다리의 상태를 추상화시켜서 표현할 수 있었다.

즉 첫 번째 테스트케이스를 보면 [7, 4, 5, 6]의 배열에서 다리의길이가 2기때문에 이렇게 표현할 수 있다.

[0, 0] -> [0, 7] -> [7, 0] -> [0, 4] -> [4, 5] -> [5, 0] -> [0, 6] -> [6] -> []

 

이 문제의 숨겨진 핵심은 trucks에 트럭이 있는데 무게때문에 못올라가는 경우에만 0을 append하는 것이다.

즉 trucks에 트럭이 없다면 0을 추가하지 않음으로써 배열이 Empty상태로 갈 수 있게 만드는 것이다.

 

어떻게 이런 생각을 했을까 신기하다.. 직접 튜플로 시간초를 담은 나와 달리 0으로 초기화된 배열을 이용해서 건너는 것을 표현한 게 인상깊었다.

 

import Foundation

func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
    var bridge = Array(repeating: 0, count: bridge_length)
    var trucks = truck_weights
    var bridgeWeight = 0
    var time = 0
    // 다리가 비어있을때까지 진행
    while !bridge.isEmpty {
        time += 1
        // 맨 앞에있는 트럭을 지워야 다리의 무게
        bridgeWeight -= bridge.removeFirst()
        
        if let t = trucks.first {
            if t + bridgeWeight <= weight {
                bridgeWeight += trucks.removeFirst()
                bridge.append(t)
            } else { //trucks에 트럭이 있는데 무게떄문에 못올라가는 경우에 0을 추가.
                bridge.append(0)
            }
        }
        
    }
    return time
}