[Python] 다리를 지나는 트럭

1) list로 해결

def solution(bridge_length, weight, truck_weights):
    t = 0           # 트럭의 탑승시점
    passing = []    # 다리 위의 트럭 리스트
    pass_time = []  # 각 트럭들의 탑승시점 리스트
    while truck_weights:
        if t != 0 and pass_time[0]+bridge_length==t:    # 타임0일 때에는 리스트 원소가 없음 and 탑승시점+다리길이=내릴 시점
            passing.pop(0)
            pass_time.pop(0)    # 트럭이 다리를 빠져나갈 때, 해당 트럭의 t도 pop!
        if truck_weights[0] + sum(passing) <= weight: # 다음 트럭을 합해도 무게제한을 넘지 않는다면 append
            passing.append(truck_weights.pop(0))    # pop 메소드 후 바로 append
            pass_time.append(t)
        t += 1
    return t+bridge_length

 

=> 적용 결과, 시간이 가장 많이 소요된 테스트케이스는

테스트 5 〉

통과 (83.42ms, 10.2MB)

 

2) 이차원 리스트

def solution(bridge_length, weight, truck_weights):
    t, on_board = 0, []   # 경과시간, 다리 위에 있는 트럭들
    while truck_weights:    # 더 이상 탑승대기 트럭이 없으면 break
        t+=1
        if sum([i for i,j in on_board])+sum(truck_weights[:1]) <= weight:   # 다음 트럭이 타도 무게를 넘지 않는다면
            on_board.append([truck_weights.pop(0),t])   # [트럭의 무게, 트럭이 탄 시점 t] append
        if truck_weights==[]:   # 더 이상 탑승대기 트럭이 없으면 break
            break
        if on_board[0][1]+bridge_length==t+1:   # 맨 왼쪽의 트럭이 내릴 시간이 되었으면 pop(0)
            on_board.pop(0)
    answer = bridge_length + on_board[len(on_board)-1:][0][1]
    return answer

=> 적용 결과, 시간이 가장 많이 소요된 테스트케이스는

테스트 5 〉

통과 (273.30ms, 10.2MB)

 

 

3) deque 활용

from queue import deque
def solution(bridge_length, weight, truck_weights):
    truck_weights, passing, time = deque(truck_weights), deque(), 0
    while True:
        if time==0: # 시작할 때, 대기트럭 하나를 passing에 추가
            passing.append([time,truck_weights.popleft()])
            time+=1
        else:   # time=1 이후부터 다음과 같이 진행
            if len(truck_weights)==0:   # 더이상 대기트럭이 없다면 time 계산후 종료
                time += bridge_length
                break
            if passing[0][0]+bridge_length==time:   # passing의 1번째가 내릴 타이밍인지 확인 후 제거
                passing.popleft()
            if sum(j for i,j in passing)+truck_weights[0]<=weight:   # 트럭 추가가능한지 확인
                passing.append([time,truck_weights.popleft()])
            
            time+=1
    return time

 

=> 적용 결과, 시간이 가장 많이 소요된 테스트케이스는

테스트 5 〉

통과 (289.55ms, 10.4MB)