다리를 지나는 트럭 : level2_파이썬

문제

https://programmers.co.kr/learn/courses/30/lessons/42583

내가 푼 풀이

print문은 내가 쉽게 이해하기 위해서 중간중간 삽입한 부분이다.

def solution(bridge_length, weight, truck_weights):
    time = 0
    n = len(truck_weights)
    bridge = [0]
    passed = 0
    bridge_weight = 0

    if bridge_length == 1:
        return len(truck_weights) + 1

    while passed < n:
        #print(time+1, "초 시작--------------------")
        if bridge[len(bridge) - 1] != 0:
            bridge_weight -= bridge.pop()
            passed += 1
            #print("도착해서 pop")
        if (len(truck_weights) != 0) and (bridge_weight + truck_weights[0] <= weight):
            bridge.insert(0,truck_weights.pop(0))
            bridge_weight += bridge[0]
            #print("트럭 더 넣어줌")
        else:
            bridge.insert(0, 0)
            #print("트럭은 더 못실어서 걍 이동만")

        time += 1
        bridge = bridge[:bridge_length]
        #print(time, "초 끝")
    return time

푸는데 한 3~4시간은 걸렸던 것 같닼ㅋㅋㅋㅋ....
처음에 문제를 이해하는 것도 어려웠다. 첫번째 입출력만 보고 문제를 이해했다고 생각했는데 2,3번째 입출력 예시를 보니 띠용?!뭔 소리지 했다..bridge_length에 대한 이해가 문제였다.
bridge_length는 다리에 올라갈 수 있는 트럭수, 즉 다리의 길이다. 그리고 트럭은 1초에 1만큼 움직인다고 생각하면 된다.
그리고 초 개념이 어려웠다. 1초 후, 2초 후.. 1~2초...솔직히 지금도 조금 헷갈리긴 하는데 그림 그려가면서 하니까 좀 이해가 됐다.
처음에 코드를 짤 때는 while문을 작성하면서도 대체 무엇을 기준으로 짜야할지 감이 잡히지 않았다. 트럭이 그냥 옮겨질 수도 있고 weight를 넘기지 않는다면 다른 트럭이 실릴 수도 있는데 모든 경우를 조건문으로 써야하나..그리고 배열이 뒤로 밀리게 하고 싶은데 어떻게 해야하지...
그래서 삽질을 엄첨 많이 했다..코드도 엄청 길었었고 답에 근접하긴 했어도 테스트 케이스를 모두 다 통과하진 못했다ㅠ그래서 다시 곰곰이 일어날 수 있는 경우를 다시 차근차근 생각해봤다.
✔ 내가 생각한 핵심은 어찌 됐든 다리 위 트럭들은 1초마다 계속 뒤로 이동한다는 점이었다. 나는 다리 위의 트럭들을 bridge배열로 만들었다. 그리고 만약 추가적으로 트럭을 실을 수 없는 경우에는 0이 bridge배열에 추가되도록 했다. 어쨌든 bridge배열은 1초마다 한칸씩 뒤로 밀린다는 점!!!이걸 깨달으니까 문제가 쉽게 풀렸다.
✔ 그리고 처음에는 굳이 bride_weight라는 변수를 따로 두지 않고 sum(bridge)로 했었는데 그렇게 하면 정확성 테스트 5번에서 시간 초과가 떴다. 찾아보니 변수를 만들어서 그 때 그 때 더하고 빼주면 시간 초과가 나지 않는다고 해서 그렇게 했더니 정말 시간 초과가 나지 않고 모든 테스트를 통과했다. sum()은 O(N)의 시간복잡도를 가져서 효율성이 낮다고 한다.