문제
https://school.programmers.co.kr/learn/courses/30/lessons/42583
문제 이해하기
- 다리 : 트럭 최대 bridge_length 개 & 트럭 무게 총합 weight 이하 무게
- 모든 트럭이 다리를 건너려면 최소 몇 초 걸리는지 구해라
문제 이해 어려움
근데 크럭 1대가 다리를 이동하는데 시간이 얼마 걸리는가?
다리를 건너는데 필요한 시간이 bridge_length만큼 드는거 같아요. 예제에서는 위 변수가 2이기 때문에 처음 무게가 7인 트럭이 지나는데 2초가 걸립니다.즉 1~2초 구간에는 무게가 7인 트럭이 다리위에 있어서 무게 4인 트럭이 다리위에 못올라가죠.3초가 됐을 대 무게가 7인 트럭이 다 지나가서 다리위에 없으므로 무게가 4인 트럭이 지나가기 시작합니다.무게가 4인 트럭은 3,4초 동안 다리를 지나고 5초가 됐을 때는 다리를 건너있게 되는거죠 (프로그래머스 해당 문제 질문하기 게시판 참고)
코드 설계
다리 : [현재 남은 시간, 트럭 무게]로 구성
다리 위에 트럭이 없을 때 (= 주어진 모든 트럭이 다리를 건널 때까지 반복)
현재 다리 위 트럭 상태 update
다리 위 기존 트럭 순차적으로 돌면서
(1) 현재 남은 시간 - 1이 0인 경우 out, 아닌 경우 남은 시간 갱신
(2) out 아닌 트럭의 갯수와 시간의 총합을 구함
out 아닌 트럭들을 다시 다리 위로 갱신
새로운 트럭이 다리에 올리기
(조건 1) 가장 첫번째로 대기 중인 트럭 무게 + 다리 위 트럭의 무게 총합이 제한을 넘지 않음
(조건 2) 다리 위 트럭 갯수 + 1 이 트럭 갯수 제한을 넘지 않음
=> 두 조건 만족하는 경우 새로운 트럭을 다리 위에 올림
구현 요점
- 중첩된 여러 리스트를 한 번에 Deque에 합성시키고자 하면 하나씩 순회로 추가하지 말고 그냥
extend사용하자 - 리스트의 첫번째 요소를 계속해서 뽑는 경우
pop(0)보다는deque의 popleft사용하자 시간 성능이 더 좋음
제출 코드
from collections import deque
def solution(bridge_length, weight, truck_weights):
answer = 1
bridge = deque()
trucks = deque(truck_weights)
w = trucks.popleft()
bridge.append([bridge_length,w])
while bridge:
answer+=1
load = []
sum_=count=0
while bridge:
time, value = bridge.popleft()
if time-1>0:
load.append([time-1,value ])
sum_+=value
count+=1
bridge.extend(load)
if trucks and sum_+trucks[0]<=weight and count+1<=bridge_length:
w =trucks.popleft()
bridge.append([bridge_length, w])
##print(truck_weights, que,answer)
return answer
