TIL 39일차 (다리를 지나는 트럭 - Kotlin)

코드카타

 

다리를 지나는 트럭

 

문제

 

테스트 케이스를 보면 트럭은 1초에 1칸씩 이동한다는 사실을 알 수 있다.

 

 

입출력 예시

 

모든 트럭의 합이 다리가 버틸 수 있는 무게 이하라면 

반환값은 (다리 길이 + 트럭 개수)에 해당한다.

 

 

풀이

class Solution {
    fun solution(bridge_length: Int, weight: Int, truck_weights: IntArray): Int {
        val bridgeQ = LinkedList<Int>() // 다리 위에 있는 트럭(무게)
        val distanceQ = LinkedList<Int>() // 각 트럭이 다리를 건너기까지의 남은 거리

        var weightSum = 0 // 현재 다리 위에 있는 트럭들의 무게합
        var time = 0 // 모든 트럭이 다리에 올라온 시점

        for (truck in truck_weights) { // 주어진 트럭을 순회하며
        
            while (true) { // 각 트럭이 다리에 진입할 수 있을때까지 반복문 실행
            
                time++ // 트럭은 1초에 1칸씩 움직인다
                
                // 맨 앞에 있는 트럭이 다리를 건넜다면 해당 트럭을 다리에서 제거
                if (distanceQ.isNotEmpty() && distanceQ.peek() == 1) {
                    weightSum -= bridgeQ.poll()
                    distanceQ.poll()
                }
                
                // 다리 위에 있는 모든 트럭들의 남은 거리를 1씩 감소
                for (i in 0 until distanceQ.size) {
                    distanceQ[i] = distanceQ[i] - 1
                }
                
                // 새로운 트럭이 다리에 진입할 수 있다면 
                // 해당 트럭을 다리에 추가 후 다음 트럭을 확인
                if (weightSum + truck <= weight) {
                    bridgeQ.add(truck)
                    distanceQ.add(bridge_length)
                    weightSum += truck
                    break
                }
            }
        }

        // 모든 트럭이 다리를 건너는 시점 반환
        return time + bridge_length
    }
}

주어진 트럭을 순회하며 각 트럭이 모두 다리에 진입하는 시점을 구한다.

while문에서는 매초 트럭이 다리를 건너는 로직을 실행시킨다.

 

트럭이 다리에 올라온 시점에서 다리 위에 있는 모든 트럭의

남은 거리를 1씩 감소하는 로직을 먼저 실행시키게 되면

다리길이가 2일때 트럭이 다리에 올라오자마자 다리에서 제거되버린다.

 

 break문을 실행하는 다음 트럭을 확인하는 로직

while문의 가장 마지막에 실행되어야 한다.

 

띠라서, 트럭이 다리를 다 건넜는지 확인 후 제거 -> 트럭의 남은거리를 1씩 감소 ->

조건 확인 후 트럭을 다리에 추가 순으로 로직을 실행해야 한다.

 

 

최종 반환값

return time + bridge_length

트럭은 1초에 한 칸씩 이동하기에 마지막 트럭이

다리를 건너는 시간(초)은 다리 길이와 일치한다.

 

따라서, 모든 트럭이 다리를 건너는 시점은

모든 트럭이 다리에 올라온 시점에서 다리길이를 더한 값에 해당한다.

 

 

회고

코드 2시간동안 쳐다봤는데 로직이 이해가 안가서

걍 떄려칠까 했는데 딴거하다가 잠깐 자고 일어나니까 이해가 됐다.

 

while문 내의 로직이 왜 저런 순서로 실행되는지

이해하는데 꽤나 골머리를 앓았던 것 같다.

 

앞으로도 머리 아프고 로직 이해안될 땐 잠시 누워있어야겠다. 

 

오늘 문제 상당히 어려웠는데 1점 주는거보면

프로그래머스 레이팅 시스템은 설계가 좀 잘못된 거 같다.