https://programmers.co.kr/learn/courses/30/lessons/42583
코딩테스트 연습 - 다리를 지나는 트럭
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈
programmers.co.kr
스택/큐를 잘 활용해야하는 문제이다.
문제를 보면 배열의 앞쪽에서 값을 많이 빼야할것 같았기에 deque 를 사용하여 효율을 높였다.
풀이:
1. 다리를 지나는 트럭을 위한 deque (d) 를 다리의 길이로 생성한다.
> 0은 차가 없는 다리 부분이다.
2. 현재 다리위에 있는 전체 무게를 초기화한다.
3. 1 에서 생성한 다리 deque (d)를 순회한다
4. 매 초마다 변화가 일어나므로 무조건 다리의 첫번째 요소를 뺀다.
> 다리의 첫번째 요소가 빈 공간이라면 차를 올릴 수 있는 경우엔 끝에 차가 올라 타는것이고, 차를 올릴수 없는 경우엔 빈 공간이 생기는 것이다
5. 전체 무게 + 첫번째 트럭의 무게가 제한무게와 같거나 더 가볍다면 첫번째 트럭을 다리위에 올려주고 전체 무게에 더한다
6. 전체 무게 + 첫번째 트럭의 무게가 제한무게보다 무겁다면 다리 끝에 빈 공간(0)을 추가한다.
> 다리위에 올릴 수 있는 차가 없는 경우이기 때문에 다리 끝에 빈공간을 추가하는것은 차들을 한칸 앞으로 전진 시켜주는 셈이 된다.
> 다리 deque (d) 를 순회하는 첫부분에 다리 맨앞에 있는 요소를 꺼내는데 이게 차라면 그 차는 통과한 것.
7. 매 순회마다 1초씩 증가한다.
from collections import deque
def solution(bridge_length, weight, truck_weights):
answer = 0
d = deque([0] * bridge_length)
truck_weights = deque(truck_weights)
total_weight = 0
while d:
total_weight -= d.popleft()
if truck_weights:
if total_weight + truck_weights[0] <= weight:
w = truck_weights.popleft()
d.append(w)
total_weight += w
else:
d.append(0)
answer += 1
return answer
# print(solution(2, 10, [7, 4, 5, 6]))
print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]))
# print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]))
# print(solution(100, 100, [10]))
# 2 10 [7,4,5,6] 8
# 100 100 [10] 101
# 100 100 [10,10,10,10,10,10,10,10,10,10] 110