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

다리를 지나는 트럭

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6] kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

 

내 풀이

일단 문제를 보고 그냥 최초에 느낀 느낌은 큐를 사용하면 좋겠다라는 생각을 했습니다. Kotlin에 Queue 클래스가 있다는 것은 알았지만 일단 사용할 줄을 몰라서 ArrayList로 큐를 구현하였습니다.

여기서 문제의 흐름을 보면 대기하는 트럭이 있고 다리를 건너 모든 트럭이 건너편에 도착할 때의 최소 시간을 구해야 합니다.

이때의 제약 조건은 다리의 길이, 트럭의 무게, 다리의 견딜 수 있는 무게라는 것을 알 수 있습니다. 여기서 트럭은 1초 동안 1 길이 만큼 이동할 수 있으므로 while 문을 통하여 1초씩 증가하며 제약 조건에 맞게 순차적으로 트럭들이 이동하는 것을 계산하였습니다.

1. 다리의 길이 만큼 큐를 만들어 0으로 초기화 (time : 경과시간, index : 현재 최우선 대기 중인 트럭의 순번)
2. index가 트럭의 갯수보다 작고 다리의 무게가 견딜 수 있는 무게보다 작다면 ➡ 큐를 한칸씩 앞으로 땡기고 index 번째 트럭 다리 진입
3. 아닐 경우 ➡ 한 칸씩 이동, 만약 이동 후에 2번 같은 상황이면 다음 트럭이 다리로 진입
4. 2~3번의 과정을 반복하다가 다리위에 트럭이 없고 마지막 트럭까지 건너가면 break
5. 최종적으로 걸린 시간을 return

📝 코드

class Solution {
    fun solution(bridge_length: Int, weight: Int, truck_weights: IntArray): Int {

    val bridgeList : ArrayList<Int> = ArrayList()
    var time = 0
    var index = 0

    for(i in 0 until bridge_length){
        bridgeList.add(0)
    }

    while(true){
        if(index < truck_weights.size && bridgeList.fold(0){acc, i -> acc+i} + truck_weights[index] <= weight ){
            bridgeList.removeAt(0)
            bridgeList.add(truck_weights[index])
            index++
        }else{
            bridgeList.removeAt(0)

            if(index < truck_weights.size && bridgeList.fold(0){acc, i -> acc+i} + truck_weights[index] <= weight){
                bridgeList.add( truck_weights[index])
                index++
            }else{
                bridgeList.add(0)
            }
        }
        time++

        if(index == truck_weights.size && bridgeList.all { it == 0 })
            break;
    }
        return time
    }
}

다른 사람의 풀이

예제 1

import java.util.*

class Solution {
    fun solution(bridge_length: Int, weight: Int, truck_weights: IntArray): Int {
        var answer = 0
        val bridgeQueue: Queue<Int> = LinkedList(List(bridge_length){0})
        val waitingQueue: Queue<Int> = LinkedList(truck_weights.toList())

        while (bridgeQueue.isNotEmpty()) {
            answer++
            bridgeQueue.poll()
            if (waitingQueue.isNotEmpty()) {
                if (bridgeQueue.sum() + waitingQueue.peek() <= weight) {
                    bridgeQueue.add(waitingQueue.poll())
                } else {
                    bridgeQueue.add(0)
                }
            }
        }
        return answer
    }
}

ArrayList보다 Queue 클래소로 큐를 구현하면 더 코드가 깔끔해지는 것을 알 수 있습니다.

배운 점

Queue 클래스의 사용법을 익힐 수 있었습니다. Kotiln에 Queue 클래스가 존재한다는 것은 알았지만 실제로 사용해본 적이 없어 이번 풀이에서는 사용을 못했습니다. 찾아보니 ArrayList로 큐를 구현하면 O(n)의 시간 복잡도가 발생하여 비효율적이라고 합니다. 다음에는 Queue를 사용해서 풀어야 하는 문제가 있다면 적극적으로 활용할 생각입니다.

Queue 클래스의 함수들을 간단히 살펴보면 다음과 같습니다.

• add(element: E) : Any type의 element를 Queue에 추가
• element() : 큐의 head를 제거하지 않고 head에 어떤 값이 들어가 있는지 알려줍니다.
• peek() : element()와 동일한 기능을 수행하지만 큐가 비어있을 경우 null을 리턴합니다.
• poll() : 큐에서 pop()과 같은 역할을 합니다. 큐가 비어있을 경우 null을 리턴합니다.