❓ 문제
🛎️ 아이디어
- bridge 길이 만큼의 deque를 생성한다.
- 모든 트럭이 다리에 올라갈 때까지 while문을 돈다.
- bridge에서 popleft를 통해 한 칸 씩 왼쪽으로 옮겨간다. (rotate와 다름. rotate는 1->2->3->1 처럼 돌기 때문)
- 새롭게 들어갈 트럭의 무게와 현재 bridge의 무게를 더해서 견딜 수 있는지 확인한다.
- 견딜 수 있다면 새롭게 들어갈 트럭의 무게를 더하고
- 견딜 수 없다면 0을 더한다.
💻 풀이
# 최대 bridge_length대 올라갈 수 있음. (다리의 길이)
# weight만큼 버틸 수 있음.
# 다리에 완전히 오르지 않았다면 무게를 무시한다.
from collections import deque
def solution(bridge_length, weight, truck_weights):
time = 0
# 현재 올라간 트럭의 무게 합
weight_sum = 0
# bridge 크기만큼의 데큐 생성
bridge = deque([0 for i in range(bridge_length)])
while truck_weights:
time += 1
weight_sum -= bridge.popleft()
# 이번에 들어갈 트럭 무게 계산
truck = truck_weights[0]
if weight_sum + truck <= weight:
weight_sum += truck
bridge.append(truck_weights.pop(0))
else:
bridge.append(0)
# 마지막 트럭이 들어간 후 완전히 나올 때 까지의 시간 더해주기 (bridge_length)
return time + bridge_length
🧩 포인트
- deque를 사용해서 popleft, append로 실제 다리를 건너는 것처럼 한다.
- 처음에 현재 bridge의 무게를 구할 때 sum() 함수를 사용했는데, 이럴 경우 시간 초과가 나기 때문에 sum을 담을 변수를 생성한 후 계산을 해줘야 한다.
'Algorithm | Language > Python' 카테고리의 다른 글
[programmers/Lv.2] 피로도 (0) | 2023.02.23 |
---|---|
[programmers/Lv.2] 땅따먹기 (0) | 2023.02.23 |
[programmers/Lv.2] 행렬 테두리 회전하기 (0) | 2023.02.23 |
[programmers/Lv.2] 후보키 (0) | 2023.02.23 |
[programmers/Lv.2] [3차] 방금그곡 (0) | 2023.02.23 |