from collections import deque
def solution(bridge_length, weight, truck_weights):
answer = 0
bridge = deque([0] * bridge_length) # 리스트보다 덱이 빠름
truck_weights = deque(truck_weights)
sum_weight = 0
while bridge:
# 첫 시작은 0 이지만, 이후를 위해 편의상 arrive로 정의
arrive = bridge.popleft()
# 다리 끝에 도착하면 bridge 덱에서 빼주면서
if arrive > 0:
# 다리 위 무게 합에서도 빼준다
sum_weight -= arrive
answer += 1
if truck_weights:
# 다리 위 무게 합 + 첫번째 대기 트럭 <= 최대 무게
if sum_weight + truck_weights[0] <= weight:
# 첫번째 대기 트럭을 다리 위에 올리고 다리 위 무게 합에 더한다
land = truck_weights.popleft()
bridge.append(land)
sum_weight += land
# 최대 무게보다 크면 뒤에 0 추가
else:
bridge.append(0)
return answer
# 테스트케이스 5번 시간초과
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:
# 다리에 0 추가
bridge.append(0)
return answer
⇒ 다리 위 무게의 합을 구할 때 sum( ) 함수를 사용하지 않고 +, - 로 계산하면 통과
풀이과정은 코드에 주석으로 달려 있으며, 혼자 풀지 못함🙁
정답은 다리에서 빼는 것부터 생각했다면, 나는 다리 위에 올리는 것부터 생각했다.
즉, 다리가 빌 때까지 (while bridge)가 아니라 대기 트럭이 없을 때까지 (while truck_weights)로 시작했다.
너무 복잡하게 생각하지 말고 효율적으로 생각해보자🤔