[PG|PYTHON] 다리를 지나는 트럭

0. 문제 

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

 

1. 문제 풀이

트럭이 다리에 올랐다가 다시 내려오는 과정에서 stack 자료 구조를 떠올렸지만 stack 자료 구조 자체에 (트럭, 상태) 값을 들여보내는 로직으로 한참 생각하다가 아이디어는 결국 인터넷에서 빌리고 만 문제였다 ㅠ.. 
0과 트럭 무게를 이용하여 다리 위의 실제 트럭 상태를 저장하며 푸는 아이디어가 매우 중요하다 !

2. 코드

아래는 시간초과 코드이다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    truck_weights = deque(truck_weights)
    answer = 0
    deq = deque([0 for _ in range(bridge_length)])
    #init
    answer+=1
    deq.popleft()
    deq.append(truck_weights.popleft())
    while sum(deq)>0:
        free_truck = deq.popleft()
        if truck_weights and (sum(deq) + truck_weights[0] <= weight):
            deq.append(truck_weights.popleft())
        else: deq.append(0)
        answer+=1
    return answer

 

정답 코드는 아래와 같다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    deq = deque(bridge_length * [0])

    temp_sum = 0
    while deq:
        answer+=1
        temp_sum-=deq.popleft()
        if truck_weights :
            if temp_sum + truck_weights[0] <= weight:
                truck = truck_weights.pop(0)
                deq.append(truck)
                temp_sum+=truck
                
            else: deq.append(0)
    return answer