문제 파악
bridge_length(다리 길이), weight(다리가 버틸 수 있는 총 하중), truck_weights(대기 중인 트럭들의 무게)가 주어졌을 때, 트럭들이 전부 다리를 건너는 데 걸리는 시간을 return하는 문제다.
핵심 규칙부터 정리하자면:
- 시간은 입력으로 주어지지 않는다. 우리가 초 단위로 시뮬레이션해서 직접 센다.
- 문제 조건상 트럭은 1초에 1만큼 앞으로 이동한다. (즉, 한 트럭이 다리를 완전히 건너려면 최소
bridge_length초가 필요) - 다리 위에는 현재 올라가 있는 트럭들의 무게 합이
weight를 넘지 않도록만 허용된다. - 트럭의 진입 순서는 반드시 유지(FIFO) 된다. (추월/재배치 없음, 여러 대 동시 진입은 가능하지만 대기열 순서는 깨지지 않는다)
예시로 이해하기
입력:
bridge_length = 2weight = 10truck_weights = [7, 4, 5, 6]
다리는 한 번에 총 10까지만 버틴다.
그래서 처음엔 7이 들어가고, 바로 4를 더 올리면 7+4=11로 한도를 초과한다.
→ 처음엔 7 혼자 다리를 건너기 시작한다.
시간 흐름을 초 단위로 보면:
- 1초:
7진입 (다리 위 합계 7) - 2초:
7한 칸 이동.4는 아직 못 들어옴(7+4>10) → 대기 - 3초:
7완전히 나감. 이제4진입 (합계 4) - 4초:
4한 칸 이동. 이제5도 진입 가능 (4+5=9 ≤ 10) → 합계 9 - 5초:
4나감,5한 칸 이동(다리 위 합계 5).6은 아직 대기 (5+6=11>10) - 6초:
5나감.6진입 (합계 6) - 7초:
6한 칸 이동 - 8초:
6나감 → 모든 트럭 통과 완료
따라서 정답은 8초.
(타임라인을 다른 방식으로 표현하면
0번째 트럭 3초 OUT → 1번째 3초 IN·5초 OUT → 2번째 4초 IN·6초 OUT → 3번째 6초 IN·8초 OUT 이고, 마지막 트럭이 빠져나간 시각이 최종 시간이다.)
코드로는 어떻게 풀 수 있을까?
들어가고 나가고의 문제니까 큐로 접근해보겠다.
time 을 1씩 올리면서 bridge 라는 큐에 truck_weights[i] 들을 넣을건데, 전체 큐의 합이 weight보다 크면 안된다.
그리고 bridge_length보다 더 많은 수의 트럭이 올라가도 안된다.
마지막 트럭이 다리 위에 올라간 시각 + bridge_length 해주면 답이다. (완전히 빠져나가야 끝이므로)
해답 및 풀이
from collections import deque
def solution(bridge_length, weight, truck_weights):
time = 0
bridge = deque([0] * bridge_length) # 큐를 다리로 놓음
cur_weight = 0 # 현재 다리의 총 하중
i = 0 # 트럭의 인덱스
n = len(truck_weights) # 트럭의 개수
while i < n or cur_weight > 0: # 건너야 할 트럭이 남아있거나, 다리위를 건너고 있는 트럭이 있으면 계속 반복문은 돈다.
time += 1 # 매 초마다 전진 처리
out = bridge.popleft() # 한 칸 전진 -> 맨 앞이 다리에서 내려감
cur_weight -= out # 내려간 트럭 무게를 총 하중에서 차감
if i < n and cur_weight + truck_weights[i] <= weight: # 트럭이 남아있고, 현재 다리의 총 무게에다가 이제 들어올 트럭을 더한 게 weight 이하라면,
bridge.append(truck_weights[i]) # 트럭 진입
cur_weight += truck_weights[i] # 진입한 트럭 하중 더해줌
i += 1 # 다음 트럭으로 인덱스 이동
else:
bridge.append(0) # 못 올라오면 빈칸을 채워준다.
return time
생각보다 어려워서 답을 봤다.
for 문 말고 while문을 사용하는 것과 추가로 while문에 or를 사용하는 것,
bridge 큐를 길이만큼 설정하는데, 트럭이 못올라올때 0을 append 해주는 것 등의 센스가 필요했던 문제인 것 같다.
Frontend Engineers