[프로그래머스] 다리를 지나는 트럭 (Python)

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

코딩테스트 연습 - 다리를 지나는 트럭

 

시간초과가 났던 코드

def solution(bridge_length, weight, truck_weights):
    answer = 1
    bridge = [0]*bridge_length
    bridge[0] = truck_weights.pop(0)
    while sum(bridge)!=0:
        for idx in range(bridge_length-1, -1, -1):
            if idx == bridge_length-1 and bridge[idx] != 0:
                bridge[idx] = 0
            elif bridge[idx] != 0:
                bridge[idx+1] = bridge[idx]
                bridge[idx] = 0
        if len(truck_weights) > 0:
            if sum(bridge)+truck_weights[0] <= weight and bridge[0] == 0:
                bridge[0] = truck_weights.pop(0)
        answer += 1

    return answer

 

수정 코드

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = [0]*bridge_length
    sum_bridge = 0
    while len(bridge):
        answer += 1
        sum_bridge -= bridge[0]
        bridge.pop(0)
        if len(truck_weights):
            if sum_bridge+truck_weights[0] <= weight:
                bridge.append(truck_weights.pop(0))
                sum_bridge += bridge[-1]
            else:
                bridge.append(0)

    return answer

 

✏️ 메모

• 테스트케이스 5번에서 계속 시간초과가 났다.
• 여러 번의 시도 끝에 sum(bridge)로 합을 구해준 게 문제인 것 같다고 느꼈다.
• sum을 쓰지 않고 sum_bridge라는 변수를 따로 사용해서 append할 땐 sum_bridge에 그 값을 더해주고, pop 할 땐 그 값을 빼주는 식으로 수정했다.
• 테스트케이스 5 시간 초과 해결!