💡문제 분석 요약

트럭이 정해진 순으로 다리를 건너는데에 걸리는 시간을 구하는 문제.

큐.

💡알고리즘 설계

문제에서 설명하는 그대로 순차적으로 bridge에 트럭을 올리고 시간이 지나면 트럭을 bridge에서 삭제하게 구현하였다.

다만 시간 복잡도가 n*n이라 시간 초과가 염려되어 모든 트럭이 bridge에 올라간 순간 반복문을 종료시켰다.

대기하는 트럭 순서대로 다리를 건너게 하는 부분은 바로 생각이 났으나 다리에 있는 트럭의 시간을 계산하는 부분이 고민되어서 트럭이 다리에 있었던 시간을 기록하기 위해 time_bridge 라는 리스트를 추가하였다.

다시보니 무지성으로 sum() 을 사용하지말고 total_weight 같은 변수를 두었으면 시간이 더 줄었을듯 하다.

💡코드

import copy

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = []
    time_bridge = []
    
    while truck_weights:
        answer += 1
        time_bridge = [x + 1 for x in time_bridge]
        copy_time_bridge = copy.deepcopy(time_bridge)
        
        for i, time in enumerate(copy_time_bridge):
            if time > bridge_length:
                time_bridge.pop(i)
                bridge.pop(i)
                
        truck = truck_weights[0]        
        if sum(bridge) + truck <= weight and len(bridge) + 1 <= bridge_length:
            bridge.append(truck)
            time_bridge.append(1)
            truck_weights.pop(0)
    
    answer += bridge_length         
    return answer

💡시간복잡도

O(nn) 안그래도 파이썬인데 nn이라 마지막 트럭이 브릿지에 올라간 순간까지만 while문을 돌려서 계산 시간을 최소화 하고자 했다.

💡 틀린 이유

틀리진 않았는데 시간이 좀 걸렸다.

💡 틀린 부분 수정 or 다른 풀이

이 풀이는 bridge에 길이만큼 0을 넣어서 시간체크와 무게체크를 동시에 할 수 있도록 하면서 시간 복잡도 까지 줄였다.