[프로그래머스] 다리를 지나는 트럭 - 파이썬(python)

 

 

나의 풀이

def solution(bridge_length, weight, truck_weights):
    count = len(truck_weights)
    crossing = [] # [트럭무게, 현재 몇칸을 지나고 있는지]
    complete = [] # 다리를 다 건넌 트럭 무게
    time = 0 

    while count != len(complete) :
     
        if truck_weights :
            if len(crossing) < bridge_length and sum([i[0] for i in crossing]) + truck_weights[0] <= weight: 
                crossing.append([truck_weights.pop(0),0])
            
        time += 1
        for i in range(len(crossing)):
            crossing[i][1] += 1
            
        if crossing[0][1] >= bridge_length :
            complete.append(crossing[0][0])
            crossing.pop(0)    
    

    return (time+1)

시간이 많이 걸렸는데, 어떻게든 해결은 했다...!

모든 트럭이 다리를 다 건널 때까지 반복문은 돌리고, 한 반복문 당 time 을 1씩 추가하였다.

만약 (건너고있는트럭개수가 < 다리길이) 이고,
(건너고있는트럭의총무게 + 내트럭 무게가 <= 다리 가중치) 이하라면
[내 트럭, 0 ] 을 건너는 트럭 리스트에 추가한다. 이때 0은 트럭이 다리에서 몇 칸을 움직였는지를 나타내는 것이다.

* 트럭은 1초에 1칸을 움직인다.

 

그런 다음 1초를 증가시키고, 건너고 있는 트럭들의 모든 1번째 인덱스에 1칸을 추가하였다. (1초에 1칸씩 이동하므로,,,)

 

마지막으로, 트럭의 1번째 인덱스, 즉 트럭이 건넌 칸의 개수가 다리의 길이이상이라면, 그 트럭은 다 건넌것이므로

다 건넌 트럭 리스트에 추가하고, 건너는 트럭 리스트에서 제거하였다.

 

 

보완할 점

• 건너는 트럭리스트, 완료된 트럭 리스트와 같은 불필요한 자료구조가 많다.
• 모든 트럭이 다 건널 때까지의 time 만큼 반복문을 돌리므로 시간이 느리다.

 

 

이를 해결하기 위해 다른 코드를 참고하였다.

 

 

 

👏🏻👏🏻다른 풀이👏🏻👏🏻

def solution(bridge_length, weight, truck_weights):
    q=[0]*bridge_length
    sec=0
    while q:
        sec+=1
        q.pop(0)
        if truck_weights:
            if sum(q)+truck_weights[0]<=weight:
                q.append(truck_weights.pop(0))
            else:
                q.append(0)
    return sec

먼저 다리의 길이만큼의 배열을 만든다. 

ex) 다리 길이가 5라면, _ _ _ _ _ 와 같은 형태로 유지된다.

_ 는 다리 한 칸을 의미하는 것으로, 트럭이 존재한다면 트럭 무게, 그렇지 않다면 0 으로 채워진다.

 

만약 무게가 7인 트럭이 건넌다면, 0 0 0 0 7 과 같은 형태가 될 것이다.

1초가 지나면 pop(0) 을 통해 0 0 0 7 _ 이 될 것이고,

이때 대기하고 있는 무게 x의 트럭이 존재한다면,

• 현재 다리위에있는 트럭의 무게합과 첫 번째 대기 트럭의 무게가 다리 가중치 이하라면, q의 마지막에 해당 트럭을 추가한다. -> 0 0 0 7 x
• 트럭이 다리를 건널 수 없다면, 0을 추가하여 다리 길이를 유지한다. -> 0 0 0 7 0

 

만약 대기하고 있는 트럭이 없다면, 더 이상 다리를 나타내는 배열 q 에는 append 되지 않고 pop(0) 을 할 것이다.

그리고, 다리 길이가 0이된다면, 반복문은 종료되며 경과시간을 리턴하게 된다.

 

 

와... 기본적인 큐 형태인데, 미처 생각하지 못했다.

다리 길이를 배열로 나타내며, pop(0) 을 통해 앞으로 이동하고, append() 를 통해 맨 뒤에 트럭이 추가되는 형태...

또한 비어있는 다리 칸에는 0으로 채움으로써 sum() 에 영향을 주지 않는 것까지.. 

완벽한 풀이이다..!