Programmers / 다리를 지나는 트럭 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 다리를 지나는 트럭 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0

    truck = deque(truck_weights)
    bridge = deque([0] * bridge_length)
    time = 0 # 몇 초가 흘렀는지 확인하기 위한 변수이다.
    current_weight = 0 # 무게를 비교할 때 사용할 것이다.

    while len(truck) > 0:
        # 현재 무게
        current_weight -= bridge.popleft()
        # 1초가 지남
        time += 1

        # 지금 현재 무게랑 나중에 들어오는 트럭의 무게를 비교한다.
        if current_weight + truck[0] <= weight:
            current_weight += truck[0]
            bridge.append(truck.popleft())
        else:
            bridge.append(0)

    time += len(bridge)

    return time

 

current_weight -= bridge.popleft() 를 통해 빠져나가는 차는 반드시 빼줘야 한다. 그리고 새로 들어가는 차는 truck[0]을 통해 무게를 비교해서 들어 갈 수 있으면 들어가면 된다.

---

※ 알아야 할 것

 

이 문제를 봤을 때 리스트(list[0]) 방법을 통해서 풀어도 똑같을 것 같았는데 달랐다. 왜냐하면 리스트에서 pop()은 시간복잡도가 O(N)이지만 deque()에서의 pop은 시간 복잡도가 O(1)이다.