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

프로그래머스 링크:https://programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭

처음에는 트럭무게만큼 더하고 빼고 해서 최소값을 구할려고 노력했었는데 결국 실패했다.

# 틀림.
#def solution(bridge_length, weight, truck_weights):
# cnt = 1
# stack=[]
#
# for i in truck_weights:
#     if sum(stack) + i > weight:
#         stack.pop(0)
#         stack.append(i)
#         cnt += 1
#     elif sum(stack) + i <= weight:
#         if len(stack) > bridge_length - 1:
#             cnt += bridge_length - 1
#             stack.pop(0)
#             stack.append(i)
#         else:
#             if len(stack) == 0:
#                 stack.append(i)
#                 cnt += bridge_length
#             else:
#                 cnt += 1
#                 stack.append(i)
#
# return cnt

중간에 이상함을 느끼고 그냥 갈아엎고 새로 만들기로했다.

 

deque를 사용해서 왼쪽을 하나씩 빼내서 시간복잡도 효율은 조금 안좋지만 확실한 방법을 사용했다.

 

from collections import deque

bridge_length = 2
weight = 10
truck_weights = [7,4,5,6]

bridge = 0
wait = deque(truck_weights)
crossing = deque([0] * bridge_length)

cnt = 0

while wait or bridge > 0:
    cnt += 1
    bridge -= crossing.popleft()

    if wait and bridge + wait[0] <= weight:
        new_weight = wait.popleft()

        bridge += new_weight
        crossing.append(new_weight)

    else:
        crossing.append(0)

print(cnt)

기차를 다리에 하나씩 올리고 crossing 배열의 0에 한칸씩 움직이게 하였다. 만약 무게가 넘어간다면 무게가 낮아질떄까지 무효값(0) 을 투여했다.

 

그리고 기다리고있는 wait배열이 없어지고 브릿지의 값이 0 이된다면 계산을 끝냈다.

 

값은 잘 바꿔서 함수로 제출하면 끝

 

효울성이 좋다고는 말 못하겠다.

다른 방법이 있다면 댓글로좀 부탁드려용