EHX.dev

[프로그래머스] 스택/큐 > 트럭

March 05, 2020

문제

최대 10,000대의 트럭(truck_weights)이 길이가 bridge_length이고 무게 가용치가 weight인 일 차선 다리를 지나간다. 트럭이 1초 당 1의 거리를 순서대로 지나갈 때, 모든 트럭이 다리를 건너려면 몇 초가 걸리는지 return 하세요.

조건

  • 다리에 올라갈 때 1초의 시간이 소요되고 이 시간에는 트럭의 무게는 고려하지 않습니다.
  • bridge_length는 1 이상 10,000 이하입니다.
  • weight는 1 이상 10,000 이하입니다.
  • truck_weights의 길이는 1 이상 10,000 이하입니다.
  • 모든 트럭의 무게는 1 이상 weight 이하입니다.

방법

  • 다리에 올라온 트럭의 무게가 다리의 무게 가용치보다 낮으면 트럭을 올리고, 올라온 시간을 기록합니다.
  • 올라간 트럭 중 맨 앞에 있는 트럭이 도착하면(경과 시간 - 출발 시간 == 다리의 길이) 최종 결과값을 도착 시간(출발 시간 + 다리의 길이)으로 업데이트합니다.
  • 마지막 트럭이 도착하면 가장 마지막에 업데이트 된 도착 시간이 최종 결과겂입니다.

문제풀이

from collections import deque


def solution(bridge_length: int, weight: int, truck_weights: list) -> None:
    answer = 0
    elapsed = 0
    truck_weights = deque(truck_weights)
    on_bridge = deque()
    entered = deque()

    while truck_weights or entered:
        elapsed += 1

        if entered and (elapsed - entered[0] == bridge_length):
            answer = bridge_length + entered.popleft()
            on_bridge.popleft()

        if truck_weights and ((sum(on_bridge) + truck_weights[0]) <= weight):
            on_bridge.append(truck_weights.popleft())
            entered.append(elapsed)
    return answer

주어진 상황이 최대 10,000대의 트럭이 지나갈 수 있다 인데, python의 기본형 배열을 사용하면 트럭이 출발, 도착할 때 배열의 index 재배열 과정에서 시간 복잡도가 크게 증가하기 때문에 메모리 사용량은 다소 올라기자만 deque를 사용하여 시간 복잡도 문제를 해결하였습니다.

테스트 코드

import unittest

from .solution import solution


class UnitTest(unittest.TestCase):
    def test_solution(self) -> None:
        self.assertEqual(
            solution(
                bridge_length=2,
                weight=10,
                truck_weights=[7, 4, 5, 6],
            ),
            8
        )
        self.assertEqual(
            solution(
                bridge_length=100,
                weight=100,
                truck_weights=[10],
            ),
            101,
        )
        self.assertEqual(
            solution(
                bridge_length=100,
                weight=100,
                truck_weights=[
                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10
                ],
            ),
            110,
        )


if __name__ == '__main__':
    unittest.main()

어려웠던 점

  • 트럭이 올라온 시간과 트럭이 나가는 시점을 구하는 부분에서 시간이 좀 걸렸다.
Written by@EHX
Software Developer, Back-End Engineer

GitHubFacebook