프로그래머스 | python | level 2 | 다리를 지나는 트럭

• 푸는 데 걸린 시간 → 2시간에서 3시간 사이

• collections 모듈의 deque를 사용해 풀었다.

• 풀이는 처음에 풀지 못하고 다른 사람의 풀이를 보고 힌트를 얻었다.

• 하지만 특정 테스트케이스에서 계속 시간초과가 나서 풀지 못하고 있었다.

• 시간 초과를 어떻게 없앨까 고민하면서, 쓸데 없는 연산에 대한 통찰이 늘었다. 아무 생각 없이 쓰고 있던 sum(bridge)가 문제였다.

• 테스트케이스 5에서 계속 막히던 코드

    from collections import deque
  
    def solution(bridge_length, weight_bridge_can_hold, truck_weights):
        time = 0
        bridge = deque([0] * bridge_length)
        truck_weights = deque(truck_weights)
  
        while True:
            time += 1
            bridge.popleft()
            if truck_weights:
                if sum(bridge) + truck_weights[0] <= weight_bridge_can_hold:
                    bridge.append(truck_weights.popleft())
                else:
                    bridge.append(0)
            else:
                time += len(bridge)
                return time

• 통과 코드

    from collections import deque
  
    def solution(bridge_length, weight_bridge_can_hold, truck_weights):
        time = 0
        bridge = deque([0] * bridge_length)
        truck_weights = deque(truck_weights)
        sum_weight_on_bridge = 0
  
        while True:
            time += 1
            sum_weight_on_bridge -= bridge.popleft()
            if truck_weights:
                if sum_weight_on_bridge + truck_weights[0] <= weight_bridge_can_hold:
                    new_truck = truck_weights.popleft()
                    bridge.append(new_truck)
                    sum_weight_on_bridge += new_truck
                else:
                    bridge.append(0)
            else:
                time += len(bridge)
                return time

  • sum(bridge)을 없애고, 다리 위의 모든 트럭의 무게의 합을 나타내는 변수를 따로 만들었다.
  • 다리에서 트럭이 나가거나 들어올 때 무게를 빼고 더하면서 sum을 통제했다.
  • 그 결과, 테스트케이스가 바로 파란불이 들어오는 걸 보면서 희열을 느꼈다.
  • 교훈: 아무리 함수가 짧고 쉬워도 쓸 데 없는 연산을 줄이자.