[알고리즘][코틀린] 프로그래머스 다리를 지나는 트럭 -스택, 큐-

https://programmers.co.kr/learn/courses/30/lessons/42583?language=kotlin#

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스

 

프로그래머스의 다리를 지나는 트럭문제를 코틀린으로 풀어보았다.

 

내가 알고리즘 초보라 그런거겠지만 레벨2 문제인데 쉽게 풀리지는 않았다. 대기큐에 트럭이 있을 경우 주석 부분을 처음에 while문 가장 앞에서 실행하여 삽질을 했었다.(그럼 로직상 틀려진다.) 

그리고 테스트케이스 설명을 보다시피 무게 6짜리가 2 길이의 다리를 건너는데 2가 아니라 3이 걸리는 것을 주의해야한다. 그래서 마지막 결과 time에 +1 을 해주었다.

 

알고리즘 연습을 많이 해봐야겠다. 

(5월에 알고리즘 복습을 하며 다시 풀어봤습니다. 테스트케이스가 추가되었다고 써있고 틀렸다길래 밑에 참고해주세요!)

 

 

설명은 주석에 적어놨습니다. 

import java.util.*

class Solution {

    fun solution(bridge_length: Int, weight: Int, truck_weights: IntArray): Int {
        val readyQueue: Queue<Truck> = LinkedList<Truck>()  //출발전 대기큐
        val onBridgeQueue: Queue<Truck> = LinkedList<Truck>() //다리위 출발큐
        var onBridgeTotalTruckWeight = 0 //다리 위 현재 무게
        var time = 0

        //값 세팅
        for (weight in truck_weights) {
            readyQueue.offer(Truck(weight, 0))
        }

        //미리 출발큐에 하나 추가
        if(readyQueue.size >= 0) {
            onBridgeTotalTruckWeight += readyQueue.peek().weight
            onBridgeQueue.offer(readyQueue.poll())
        }else{
            return 0
        }

        while (!onBridgeQueue.isEmpty()) {
            //다리 위 트럭이동
            for (truck2: Truck in onBridgeQueue) {
                truck2.postion++
            }
            //도착한 트럭 빼기
            if (onBridgeQueue.peek().postion >= bridge_length) {
                onBridgeTotalTruckWeight -= onBridgeQueue.poll().weight
            }
            //대기큐에 트럭이 있을 경우
            if (!readyQueue.isEmpty()) {
                // 다리가 무게 견딜수 있는 트럭인 경우 트럭 poll(출발)
                if (readyQueue.peek().weight + onBridgeTotalTruckWeight <= weight) {
                    with(readyQueue.poll()){
                        onBridgeTotalTruckWeight += this.weight
                        onBridgeQueue.offer(this)
                    }
                }
            }
            //총 걸린 시간 증가(결과)
            time++
        }

        return time + 1 //마지막 빠져나오는 시간떄문에 +1
    }

    //트럭무게, 현재위치
    data class Truck(var weight: Int, var postion: Int)
}

 

 

 

[2020-05-08 업데이트]

알고리즘 복습을 하던 도중 2020.04.06 테스트케이스가 추가 되었다는 공지를 보고 다시 실행해봤는데 테스트케이스 4번이 틀렸다고 나왔습니다. 근데 제출하기를 눌렀을 때는 여전히 통과했습니다. 이것도 이상한거지만 무시하고 실행하기의 테스트케이스 4를 위해 문제를 다시 풀어봤습니다. 

근데 다시 풀고 예외처리를 해도 테스트케이스 2와 4가 서로 엇갈려서 틀리게 나왔습니다.

 

계속 해도 안되어서 다시 테스트케이스를 봤는데

보다시피 테스트 케이스 2와 4는 트럭 길이가 하나일 때이며 이때는 당연히 기차 길이의 + 1 만큼의 시간이 답으로 나와야합니다. 그런데 둘은 기댓값부터 다릅니다. 제 생각에는 새로 추가된 테스트케이스가 틀린 것 같아 일단 질문하기에 테스트케이스가 이상한 것 같다고 남긴 상태입니다. 나중에 댓글이 달리면 확인해보도록 하겠습니다.

 

 

일단 다음과 같이 풀었습니다.( 이전 코드보다 조금 더 정리됬습니다. 필요없는 코드 삭제)

import java.util.*

class Solution {

    fun solution(bridge_length: Int, weight: Int, truck_weights: IntArray): Int {
        val readyQueue: Queue<Truck> = LinkedList<Truck>()  //트럭 대기큐
        val onBridgeQueue: Queue<Truck> = LinkedList<Truck>() //다리위 트럭 출발큐
        var onBridgeTotalTruckWeight = 0 //다리 위 현재 무게
        var time = 0

        //값 세팅
        for (weight in truck_weights) {
            readyQueue.offer(Truck(weight, 0))
        }

        while (true) {
            //대기큐에 트럭이 있을 경우
            if (readyQueue.isNotEmpty()) {
                // 다리가 무게 견딜수 있는 트럭인 경우 트럭 poll(출발)
                if (readyQueue.peek().weight + onBridgeTotalTruckWeight <= weight) {
                    with(readyQueue.poll()) {
                        onBridgeTotalTruckWeight += this.weight
                        onBridgeQueue.offer(this)
                    }
                }
            }
            //다리 위 트럭이동
            for (truck2: Truck in onBridgeQueue) {
                truck2.postion++
            }
            //도착한 트럭 빼기
            if (onBridgeQueue.peek().postion >= bridge_length) {
                onBridgeTotalTruckWeight -= onBridgeQueue.poll().weight
            }
            //총 걸린 시간 증가(결과)
            time++
            // 다 끝난 경우
            if(readyQueue.isEmpty() && onBridgeQueue.isEmpty()){
                break
            }
        }
        return time + 1//마지막 빠져나오는 시간떄문에 +1
    }

    //트럭무게, 현재위치
    data class Truck(var weight: Int, var postion: Int)
}

 

 

 

댓글과 공감은 큰 힘이됩니다. 감사합니다.!