[알고리즘] 다리를 지나는 트럭(⭕) - 알고리즘 공부

✔️사이트 : 프로그래머스

✔️언어 : Kotlin

✔️난이도 : Level 2

✔️문제 : 다리를 지나는 트럭

 

총평 :

초보라서 체감난이도는 3~4 쯤이지 않을까라는 생각을 했다.

 

 

과정 :

해당 문제에서는 경과 시간에 맞춰서 다리를 건너는 트럭 을 어떻게 구현하는지가 관건이었다.

트럭위를 지나가는 형태의 다리를 어떤 데이터 구조체를 사용해야할지 해결하는게 제일 어려웠습니다. 그래서 배열, 리스트를 시도하다가 떠오른게 Queue 였으며 다음과 같은 아이디어를 생각했으며 구현했다.

 

조건 :

- 다리 길이 2

- 한계 무게 10

- 대기 트럭 (7,4,5,6)

 

최소 트럭의 무게가 1 이상이니, 다리 Queue 를 0 으로 채워서 표현했다. 그리고 길이가 2이고 0으로 채워진 Queue 에서 poll 후에 트럭을 add 하는 형태를 했다.

0	0
0	7
7	0
0	4
4	5
5	0
0	6
0	0

 

 

 

 

테스트 코드

import java.util.*

@Test
fun test() {
  assertEquals(8, solution(2, 10, intArrayOf(7, 4, 5, 6)))
  assertEquals(101, solution(100, 100, intArrayOf(10)))
  assertEquals(110, solution(100, 100, intArrayOf(10, 10, 10, 10, 10, 10, 10, 10, 10, 10)))
}

private fun solution(bridge_length: Int, weight: Int, truck_weights: IntArray): Int {
  var answer = 0
  val truckList = truck_weights.toMutableList()
  val bridgeQueue = LinkedList(Array(bridge_length) { 0 }.toList())

  while (truckList.isNotEmpty() || bridgeQueue.sum() != 0) {
    answer++
    bridgeQueue.poll()

    if (truckList.isNotEmpty() && (bridgeQueue.sum() + truckList[0] <= weight)) {
      bridgeQueue.add(truckList[0])
      truckList.removeAt(0)
    } else {
      bridgeQueue.add(0)
    }
  }

  return answer
}

 

 

테스트 결과

 

 

비슷하지만 더 나아보이는 다른 사람 코드

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
    }
}