0. 문제설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
| 경과 시간 | 다리를 지난 트럭 | 다리를 건너는 트럭 | 대기 트럭 |
|---|---|---|---|
| 0 | [] | [] | [7,4,5,6] |
| 1~2 | [] | [7] | [4,5,6] |
| 3 | [7] | [4] | [5,6] |
| 4 | [7] | [4,5] | [6] |
| 5 | [7,4] | [5] | [6] |
| 6~7 | [7,4,5] | [6] | [] |
| 8 | [7,4,5,6] | [] | [] |
따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.
solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.
제한 조건
- bridge_length는 1 이상 10,000 이하입니다.
- weight는 1 이상 10,000 이하입니다.
- truck_weights의 길이는 1 이상 10,000 이하입니다.
- 모든 트럭의 무게는 1 이상 weight 이하입니다.
1. code
from collections import deque
def solution(bridge_length, weight, truck_weights):
answer = 1 #sec
truck_weights = deque(truck_weights)
on_weight = truck_weights.popleft() #다리 위 트럭무게의 합
on_trucks = deque([[on_weight, 0]]) #다리 위의 트럭
while(on_trucks):
answer += 1
for truck in on_trucks:
truck[1] += 1
if (on_trucks[0][1] == bridge_length):
on_weight -= on_trucks.popleft()[0]
if (truck_weights and on_weight+truck_weights[0] <= weight):
on_weight += truck_weights[0]
on_trucks.append([truck_weights.popleft(), 0])
return answer
2. 문제풀이
자료구조
on_weight = 다리 위 트럭무게의 합on_trucks = [[트럭 무게, 다리 위 트럭의 위치]]
다리 위 트럭의 위치 범위는 0 ~ bridge_length -1 이다.
다리 위 트럭의 위치가 bride_length인 경우 다리를 다 건넌 트럭이다.
설명
다리 위 트럭무게의 합이 weigth 이하인 경우 on_trucks에 append(). 다리 맨 끝에 있는 트럭의 위치가 bride_length인 경우 on_trucks에서 pop()
on_trucks의 트럭들의 위치는 1초마다 1씩 증가한다.
모든 트럭이 다리를 건넌 경우 answer를 반환한다.
3. 새로운 사실
딱히 없네요
4. 주저리
지난번에 새롭게 알게된 deque를 요긴하게 썼다.
다리 위 트럭의 위치를 증가시키는 방식은 시간복잡도와 공간복잡도 모두에서 비효율적이지만 알아보기는 쉽기도 하고 다른 방식으로 구현하기 귀찮아서 이렇게 풀었는데..
생각보다 시간차이가 좀 나서 반성했습니다.
