문제 - 다리를 건너는 트럭
* 문제 설명
트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다.
모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다.
트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.
다음은 [7,4,5,6] 순으로 대기 중인 트럭들이 최단시간으로 다리를 건너는 방법입니다.
* 제한 조건
- bridge_length는 1 이상 10,000 이하입니다.
- weight는 1 이상 10,000 이하입니다.
- truck_weights의 길이는 1 이상 10,000 이하입니다.
- 모든 트럭의 무게는 1 이상 weight 이하입니다.
문제 풀이법
조건
- total_weight(다리 위에 올라와있는 트럭의 총 무게) 는 항상 bridge_weight보다 같거나 작아야 함
- 각 트럭은 bridge_length만큼의 시간이 자나야 탈출 가능함.
-> 즉, 트럭 1대만 대기 중인 상태라면 answer = bridge_length - 문제에서 제공해 준 아이디어를 사용.
-> 다리를 건너는 트럭 리스트 on = deque()
다리를 지난 트럭 리스트 off = []
- 꼭 필요한 전제 : truck_weights가 empty일 때까지 계속 연산해야함.
코드 설명
-
위에 언급한 꼭 필요한 전제를 while문의 조건으로 건다.
-
while문을 돌 때마다 answer(시간)++한다 === 시간이 1초씩 흐른다.
-
처음 리스트on은 비어있지만, 조건1을 만족시키는 한 truck_weights의 첫 인덱스, 즉 처음 기다리고 있는 트럭이 다리에 올라가며 on.append()된다.
-
각 트럭은 bridge_length만큼만 리스트on에 있으면 되기 때문에 on의 길이가 bridge_length가 되면 리스트on의 맨 앞 트럭은 off로 빠진다.
-
on.append(0)해주는 이유 : [이미 다리 위에 있는 트럭의 총 무게 + 앞으로 들어올 트럭의 무게]가 weight보다 클 경우, 앞으로 들어올 트럭은 다리로 진입하지 못하고 대기해야 한다. 대기 중일 때도 시간은 흘러야 하므로 0을 넣는다.
-
while문의 조건은 리스트 truck_weights가 true일 때까지 즉, while문이 끝난 후의 truck_wegiths의 길이는 1이다.
이 때, 대기 중인 트럭이 1개인 경우는 별도의 연산이 필요없으므로 answer에 bridge_length만큼만 더해준다.
***
어려웠던 점
- 리스트 truck_weights의 길이를 무조건 0으로 만들려고 했었다. 그래서 계속 해당 리스트의 인덱스 [0]에 접근할 수 없었고 pop()또한 사용이 어려웠다.
여기서 단순히 answer += bridge_length만 해주면 해결가능했는데 그걸 생각하지 못하고 끝까지 while문 안에서 끝을 보려고 했었다. 조금 더 시야를 넓게 가지고 생각하면 좋을 듯 하다.
배운 점
- list.pop(0)은 성능이 매우 좋지 않아, while문 안에 들어가게 되면 O(1)로도 해결할 수 있는 문제가 O(n)이 된다고 한다. 이는 sum(list)도 마찬가지.
- 원래 sum(on)으로 현재 다리 위 트럭의 총 무게를 계산하려 했으나, sum(list)를 사용하지 않기 위해 total_weight를 사용했다.
- 마찬가지로 pop(0)을 사용하지 않기 위해 pop(0)이 꼭 필요했던 on을 deque로 만들어 popleft()를 사용했다.
