[파이썬] 프로그래머스 - 다리를 지나는 트럭

---

📌  풀이 1 (테스트 케이스 5 시간 초과)

 

큰 생각의 흐름은

"큐를 다리라고 생각하고 공기(0)들을 미리 채운 다음에 매 시간마다 pop 하고 현재 다리 위의 무게에 따라 트럭을 push 하거나 공기(0)를 push 한다"이다.

 

 

우선 queue를 양방향에서 처리해야 하기 때문에 양방형 처리에 유리한 deque를 사용했다.

 

공기(0)들을 미리 채우기 위해

 

truck_bridge_deque = deque(bridge_length * [0])

 

을 통해 truck_bridge_deque를 설정해준다.

 

 

while len(truck_bridge_deque)를 통해 다리 위에 있는 트럭이 모두 사라질 때까지 while문을 반복한다.

if문에서는 대기 중인 트럭 즉  truck_weights_deque가 존재하는지 여부를 확인하고 이때 truck_bridge_deque 즉 다리 위에 있는 모든 트럭의 무게와 truck_weights_deque의 가장 앞에 있는 트럭 즉 다리에 올라오기 직전의 트럭의 무게의 합이 한계 무게를 넘지 않는지 체크한 뒤 넘지 않는다면 

 

truck_bridge_deque.append(truck_weights_deque.popleft())

 

을 통해 다리 위로 올려준다. 즉 truck_bridge_deque에 append를 해준다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    truck_bridge_deque = deque(bridge_length * [0])
    truck_weights_deque = deque(truck_weights)
    while len(truck_bridge_deque):
        answer += 1
        truck_bridge_deque.popleft()
        if truck_weights_deque:
            if sum(truck_bridge_deque) + truck_weights_deque[0] <= weight:
                truck_bridge_deque.append(truck_weights_deque.popleft())
            else:
                truck_bridge_deque.append(0)
    return answer

 

 

 

 

 

 

📌  풀이 2

하지만 위의 코드로는 테스트 케이스 5에서 시간 초과가 발생했다.

sum의 시간 복잡도가 O(N)이기 때문에 발생하는 시간 초과였다.

 

따라서 아래와 같이 temp를 통해 임시로 전체 무게를 따로 관리해주었다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    temp = 0
    truck_bridge_deque = deque(bridge_length * [0])
    truck_weights_deque = deque(truck_weights)
    while len(truck_bridge_deque):
        answer += 1
        temp -= truck_bridge_deque[0]
        truck_bridge_deque.popleft()
        if truck_weights_deque:
            if temp + truck_weights_deque[0] <= weight:
                temp += truck_weights_deque[0]
                truck_bridge_deque.append(truck_weights_deque.popleft())
            else:
                truck_bridge_deque.append(0)
    return answer