❓프로그래머스 : 다리를 지나는 트럭
〽️ 문제 요약
다리가 weight 이하의 무게를 버틸 수 있을 때, 트럭 여러대가 모두 다리를 건너려면 최소 몇 초가 걸리는지 구하면 되는 문제
🤨 접근법
문제를 푸는데 막 특별하거나 어려운 테크닉이 필요하지는 않지만 전반적인 문제 개념을 이해하는 데 어려웠던 문제였다. 트럭이 다리에 완전히 올라가야 된다는 조건은 주어졌지만, 다리의 길이는 주어지는데 트럭의 길이는 왜 안주어지는지 등등..
결론적으로는 트럭은 모두 길이가 1이라고 가정하고 1초에 한칸씩 움직인다고 생각하면 된다. 이제 다음 애매한 점은 트럭이 다리를 지나가는 것을 어떻게 표현하는가 이다.
여기는 큐를 다리 길이만큼 0으로 채워서 활용하는 테크닉이 활용될 수 있다. 별도로 다리의 무게를 관리하는 변수를 두고 매 1초마다 다음의 과정을 수행한다.
- 큐(다리)에서 원소를 하나 pop해서 무게 변수에서 값만큼 빼준다.
- 트럭이면 다리 무게가 트럭만큼 줄어들고, 0이면 변화가 없다.
- 맨 앞 트럭을 다리(큐)에 올렸을 때 무게가 weight 이하라면 트럭의 무게를 다리(큐)에 append한다.
- 맨 앞 트럭을 다리(큐)에 올렸을 때 무게가 weight보다 크다면 0을 append한다.
위 과정을 모든 트럭이 전부 다리에 올라갔을 때까지 진행하고, 마지막 트럭이 올라가면 그 트럭이 다리를 빠져나오는 데 다리 길이만큼 소요되므로 최종 시간에 다리 길이만큼을 더해준다.
🔡 코드
from collections import deque
def solution(bridge_length, weight, truck_weights):
trucks = deque(truck_weights)
on_bridge = deque([0 for _ in range(bridge_length)])
sum_on_bridge = 0
answer = 0
while trucks:
answer += 1
sum_on_bridge -= on_bridge.popleft()
if trucks and sum_on_bridge+trucks[0] <= weight:
sum_on_bridge += trucks[0]
on_bridge.append(trucks.popleft())
else:
on_bridge.append(0)
return answer+bridge_length📚 고찰
큐, 덱을 활용하는데 어려움은 없었으나 문제를 해결하도록 코드를 동작시키는데 어려움이 많았던 문제였다. 프로그래머스 문제들은 체감상 이런 문제가 대부분인 것 같은데, 더 집중해서 문제를 읽고 가능한 빨리 문제를 이해하는게 중요할 것 같다.
Grow Exponentially