다리를 지나는 트럭

16616516·2020년 9월 30일
0

알고리즘

목록 보기
9/16

고민을 해 보았지만 도저히 어떻게 풀어야할 지 감이 안왔다.
정답을 보니 좀 신기했고, 문제를 많이 접하다 보면 언젠가 나도 이런 추리를 할 수 있기를 빌어본다.

정답 코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    time = 0
    wnum = 0
    bridge_sum = 0
    bridge = deque([0] * bridge_length)
    while wnum < len(truck_weights):
        time+=1
        bridge_sum -= bridge.popleft()
        if (bridge_sum + truck_weights[wnum]) <= weight:
            bridge.append(truck_weights[wnum])
            bridge_sum+= truck_weights[wnum]
            wnum+=1
        else:
            bridge.append(0)

    return time + bridge_length

문제의 해결 방법은 의외로(?) 간단했다.

풀이

1) 정답 time변수, 지나간 트럭수를 세면서 동시에 index역할을 하는 wnum, 다리 무게의 총 합을 가진 bridge_sum, 실제 다리를 묘사하는 birdg

아마 bridge를 떠올리는데 이 문제의 관건이 아닌가 싶다.
bridge는 deque에 모두 [0]을 넣어 초기화시킨다.

2) 나간 트럭의 수와 truck_weights의 길이를 비교하는 while문을 만들고
한칸을 빼고 넣을 수 있는지 없는지 확인한다.
넣을 수 있으면 넣고, 무게를 증가시키고, 인덱스를 증가시킨다.
넣을 수 없다면, 0을 넣는다.

3) 이런 식으로 반복하다 while문이 종료되면 마지막 차가 다리 위에 막 올라간 상태가 되므로
다리의 길이만큼을 다시 더한 time값을 리턴하면 된다.

느낀 점

꽤나 어렵다..
괜히 level2가 아닌가 싶기도하고.. 자신감도 많이 떨어졌다.

profile
열심히 사는 사람

0개의 댓글