프로그래머스(다리를 지나는 트럭) with python

• 문제 설명

트럭은 주어진 truck_weights 배열에 있는 대수만큼 있으며 해당 순서대로 weight가 주어져있다

트럭은 1초에 1씩 다리를 지날 수 있다

다리는 주어진 weight만큼만 무게를 견딜 수 있다

이 때 모든 차량이 다리를 빠져나갈 때까지의 최단 시간은 얼마인가?

 

• 솔루션

해당 문제를 풀 때 삽질을 해서 3중 for문을 써서 풀었지만 어리석은 일이었다

처음에는 시간이 일정하게 흐르기 때문에 시간 배열을 따로 생성하여 차량들이 계속해서 1씩 진행하고 있는

식으로 생각하였으나 이 경우 시간 복잡도에서 문제가 발생되었다.

이 문제는 최소 시간 복잡도가 O(N^2)은 되어야 하는 문제이다

따라서 생각을 바꾸어 다리 위에 있는 차량들만을 생각하여 해당 차량들의 총합계+들어올 차량의 무게가

주어진 weight를 넘지 않을 때라는 조건으로 만들어주고 그 이외의 경우에는 weight를 0으로 하여 실제로는

들어오지 않는 것으로 간주하고 이 때 차량의 대수가 bridge_length와 동일한 경우 한 대씩 차량을 빼주는 것으로 생각하였다

이는 즉, 다리에 차량이 가득 채워져 있을 때 한 대를 밀어낸다는 개념으로 생각하면 된다

따라서 이렇게 진행하게 되면, 문제가 비교적 간단하게 해결될 수 있다.

 

def solution(bridge_length,weight,truck_weights):
    time=0
    go_truck=[] # 다리를 건너고 있는 차

    for tw in truck_weights:
        q_truck=1
        while q_truck!=0:
            if len(go_truck)==bridge_length:
                go_truck.pop()
            
            # weight보다 go_truck에 있는 합이 더 작으면 append 시켜준다
            if sum(go_truck)+tw<=weight:
                time+=1
                q_truck=0
                go_truck.insert(0,tw) # 시간,트럭의 weight
            else:
                time+=1
                q_truck=1
                go_truck.insert(0,0)

    answer=time+bridge_length
    return answer

이는 해당 코드로, 여기서 while문의 경우, q_truck이라는 변수를 집어넣어, 무게를 만족시키지 못해 차량을 밀어넣지 못할 경우 차량을 밀어넣을 수 있을 때까지 반복해주기 위한 장치이다.