프로그래머스 L2 - 다리를 지나는 트럭
풀이
- 대기 트럭 리스트
- 현재 다리 리스트
- 현재 무게
이렇게 세 가지가 필요했음
- while loop는 현재 다리만큼 돈다
현재 다리에 아무것도 없다면 더 이상 지나갈 트럭이 없으니 종료 - 첫 트럭이 올라가는 시점부터 시간 +
- 현재 무게에서 현재 다리에서 빠질 트럭의 무게를 뺀다
- 대기 트럭이 비지 않고 현재 무게와 새로 들어올 트럭의 무게가 다리 무게보다 낮다면
새 트럭을 넣어주고 현재 무게에 더한다 - 무게가 낮지 않다면 다음에 들어올 트럭이 없으므로 0을 넣어준다
- 반복
풀면서 sum() 함수를 사용하고, 미리 시간을 계산하지 않고 따로 계산했더니
시간초과가 계속 발생했다.
input이 10,000이기 때문에 O(N)을 넘어서는 안된다
코드
from collections import deque
def solution(bridge_length, weight, truck_weights):
answer = 0
waited_truck = deque(truck_weights)
cur_bridge = [0] * bridge_length
cur_weight = 0
while cur_bridge:
cur_weight -= cur_bridge.pop(0)
if waited_truck:
if(cur_weight + waited_truck[0]) <= weight:
cur_weight += waited_truck[0]
cur_bridge.append(waited_truck.popleft())
else:
cur_bridge.append(0)
answer += 1
return answer
Author And Source
이 문제에 관하여(프로그래머스 L2 - 다리를 지나는 트럭), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@agugu95/L2-Truck-passing-the-Bridge저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)