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

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

프로그래머스

 

 

 

 

해결 방법:

자동차 길이를 1로 생각해보자. 자동차가 3의 길을 지난다고 상상해보자 그러면 시간대 대로 그리게 된다면 이렇게 된다

0초 : ⬜️ | ⬜️ ⬜️ ⬜️ | ⬛️

1초 : ⬜️ | ⬜️ ⬜️ ⬛️ | ⬜️

2초 : ⬜️ | ⬜️ ⬛️ ⬜️| ⬜️

3초 : ⬜️ | ⬛️ ⬜️ ⬜️| ⬜️

4초 : ⬛️ | ⬜️ ⬜️ ⬜️| ⬜️

 

 

이 그림을 보면 알 수 있듯이 자동차가 시작지점에서는 0초에는 자동차 전면부가 출발선에 있고, 1초에는 자동차 후면부가 출발선에 있다. 이를 활용하여 생각했다. 만약 자동차 전면부가 도착지점에 닿게 되면서 값이 닿게 되는 순간(자동차가 도착지점을 밟는 순간), 만약 새로운 자동차를 추가할 수 있다면 새로운 자동차를 추가하게 된다. 

이렇게 반영된다.

따라서 코드를 작성함에 있어서 도착점을 밟은 상태에서 생각을 하면 편하다. 이것을 코드로 나타냈을 때

func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
    var curQ:[[Int]] = []
    var time = 0
    var modQ:[Int] = truck_weights
    var curWeight = 0
    while !curQ.isEmpty || !modQ.isEmpty {
        while !modQ.isEmpty && modQ[0] + curWeight <= weight { // 자동차를 추가할 수 있는지 확인
            let node = modQ.removeFirst()
            curQ = curQ.map{ temp in //자동차를 추가할 때 1만큼 이동하니 그것을 반영한다.
                return [temp[0], temp[1] + 1] //자동차의 무게와, 전면부 위치를 나타내는 Queue이다.
            }
            curQ.append([node, 1]) //새로운 자동차를 추가한다. 추가하는 값은 [무게, 전면부 위치 == 1]
            curWeight += node //현재 가능한 무게를 갱신한다.
            time += 1 //1만큼 이동했으니 1만큼 시간을 앞으로 이동한다.
            if curQ[0][1] == bridge_length { //만약 현재 위치에서 전면부가 도착선과 맞닿아 있다면
                //추가할 수 있는 자동차가 있어도 반복문을 break한다.
                break
            }
            
        }
        
        let node = curQ.removeFirst()
        let curTime = bridge_length - node[1] //도착선과 자동차 전면부 사이의 거리를(시간을) 계산한다.
        curWeight -= node[0] //무게를 갱신한다.
        time += curTime //전면부와 도착선 사이의 거리(시간)를 계산한다.
        curQ = curQ.map{ temp in
            return [temp[0], temp[1] + curTime]
        } //걸린 시간 만큼 값을 더해준다.
        
    }
    time += 1 //마지막 자동차를 반영한다.
    return time
}

 

추가 설명을 하자면, 맨 앞 자동차 전면부와 도착선 사이의 거리를 계산하고 자동차를 빼버린다. 그 후 새로운 자동차를 추가하면서 현재 있는 자동차들의 거리를 더해준다. 끝까지 갔을때 마지막 자동차 전면부는 도착선에 맞닿아 있기에 그것을 반영하는 코드를 작성한다.