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

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

프로그래머스

---

나의 풀이

처음에는 묶음 단위로 차가 지나가는 줄 알고 그에 맞게 코드를 작성했었음

1	2	3
7	4,5	6

묶음 단위로 문제 풀고 위의 방식이 아니라 첫 번째 차가 빠져나가고 weight를 비교하여 바로 새로운 차가 들어가는 구조인걸 알았음

---

• truck_weights = [1,8,1,1,5,1] 
• weight = 10
• bridge_length = 4

시간
1	1
2	8	1
3	1	8	1
4		1	8	1
5	1		1	8
6	5	1		1
7	1	5	1
8		1	5	1
9			1	5
10				1
11

return 11

---

• bridge_length에 맞게 다리를 list로 생성해 준다
• bridge.pop(0)을 통해 도로를 빠져가는 작업을 해주고 조건에 맞다면 truck_weight를 넣어주고 맞지 않다면 0을 넣어주어 이동시킨다
• stack와 Queue이 섞인 느낌

sum() 사용 시 원래 테스트 5에 시간초과가 발생했었는데 다 풀고 다시 돌리니 발생하지 않았지만 9856으로  brigdge_length가 길면 길수록 시간이 오래 걸림 while문이 돌아갈 때마다 sum을 구하기 위해 for문을 한번 더 돌기 때문

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = [0]*bridge_length
    while bridge:
        bridge.pop(0)
        answer += 1

        if truck_weights:
            if sum(bridge)+truck_weights[0] <= weight :
                bridge.append(truck_weights.pop(0))
            else:
                bridge.append(0)

    return answer

---

truck_sum -= bridge[0]
truck_sum += bridge[-1]

위의 코드를 통해 시간복잡도를 줄임

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = [0]*bridge_length
    truck_sum = 0
    while bridge:
        truck_sum -= bridge[0]
        truck_sum += bridge[-1]
        bridge.pop(0)
        answer += 1

        if truck_weights:
            if truck_sum+truck_weights[0] <= weight :
                bridge.append(truck_weights.pop(0))
            else:
                bridge.append(0)

    return answer