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

 

[문제소개] 

트럭을 1칸, 다리를 N (문제의 bridge_length) 칸이라고 했을 때 각 트럭 무게와 다리 무게제한을 고려하여 모든 트럭이 지나가는 데 걸리는 초를 구하는 문제

코딩테스트 연습 - 다리를 지나는 트럭

 

 

[나의 풀이]

일단 매 초마다 루프를 돌면서 각 반복마다 일차원 조회를 하면 O(N^2) 이고 N 이 10000이므로 시간초과가 날 가능성 때문에 O(N) 으로 풀 수 있는 방법을 고민했다.

그렇다 해도 입력에 따라 결과가 달라지고 경우의 수도 많으므로 시뮬레이션을 돌려야한다고 생각했다.

처음엔 다리위로 올라온 트럭의 위치를 저장하는 자료구조를 따로 만들려고 했지만

큐에 더미데이터를 넣어서 (메모리가 아깝지만 시간을 개선할 수 있다.) 트럭의 위치를 간단하게 알아내는 방법을 사용해봤다. 

정확히는 트럭의 위치를 알 필요도 없다.

 

넣고 빼는 순서가 이 방식의 주의점인 것 같다.

먼저 뺄 수 있으면 빼고 그 다음 넣을 수 있으면 넣는다.

빼는 게 먼저오는 이유는 넣는 과정에서 무게 제한을 비교하기 때문이다. 

빼지 않고 무게 제한을 비교하면 다음 오는 트럭이 1초 딜레이 되어 답이 틀릴 것이다.

 

 

[코드]

import java.util.*

class Solution {
    fun solution(bridge_length: Int, limit: Int, truck_weights: IntArray): Int {
        var answer = 0
        var cur = 0
        var weightSum = 0
        val q = LinkedList<Int>() as Queue<Int>
        
        while(true) {
            answer += 1
            
            // 먼저 뺀다.
            if (q.size  >= bridge_length) {
                val item = q.poll()
                if (item >= 0) {
                    weightSum -= truck_weights[item]

                    if (item  == truck_weights.size - 1) break
                }
            }

            // 그리고 넣는다.
            if (cur < truck_weights.size && weightSum + truck_weights[cur] <= limit) {
                q.add(cur)

                weightSum += truck_weights[cur]
                cur += 1
            } else {
                q.add(-1)
            }
        }
        return answer
    }
}

 

 

[개선]

코드를 더 깔끔하게 개선해보았다.

큐에 넣는 내용을 index 가 아닌 각 트럭의 무게로 바꾸고

현재 다리 위에 있는 트럭 무게의 합에 그대로 더해주었다. (0이 덧셈의 항등원이니까)

 

import java.util.*

/**
 * 2021.01.01 다리를 지나는 트럭
 * https://programmers.co.kr/learn/courses/30/lessons/42583
 * 큐에 더미를 넣는 방식으로 트럭의 위치를 잡아주었음
 */
class Solution {
    fun solution(bridge_length: Int, limit: Int, truck_weights: IntArray): Int {
        var answer = 0
        var cur = 0
        var weightSum = 0
        val q = LinkedList<Int>() as Queue<Int>

        do {
            answer += 1

            if (q.size >= bridge_length) {
                val w = q.poll()
                if (w >= 0) weightSum -= w
            }

            if (cur < truck_weights.size && weightSum + truck_weights[cur] <= limit) {
                q.add(truck_weights[cur])
                weightSum += truck_weights[cur]
                cur += 1
            } else {
                q.add(0)
            }

        } while (weightSum != 0)

        return answer
    }
}