[프로그래머스 코딩테스트 연습] 다리를 지나는 트럭 (Python3)

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

프로그래머스

# 1트 (돌아가긴 하나 비효율)
from collections import deque
def solution(bridge_length, weight, truck_weights):
    i, cnt, flag = 0, 0, True
    time, queue = deque(), deque()
    while True:
        cnt += 1
        time = deque([t+1 for t in time])
        if time and time[0] >= bridge_length:
            queue.popleft()
            time.popleft()
        if flag and len(queue) < bridge_length:
            w = truck_weights[i]
            if sum(queue) + w <= weight:
                queue.append(w)
                time.append(0)
                i+=1
                if i==len(truck_weights): flag=False
        if not flag and not queue: break
    return cnt

⚡️ 나의 1트 코드의 문제점

1. sum(queue) 사용으로 매번 다리 위의 총 무게 계산 (O(N)) → 비효율적
   • sum(queue)는 매번 리스트의 모든 요소를 더하는 연산이므로, 시간 복잡도가 O(N)
   • 트럭이 많을수록 성능 저하 발생
2. time 리스트를 매번 새로 생성 (O(N)) → 비효율적
   • time = deque([t+1 for t in time]) → 리스트 전체를 다시 만들면서 메모리 낭비
3. 불필요한 조건문 (flag 체크)
   • flag = False는 사실 필요 없음 → i == len(truck_weights)일 때 break 가능

# 리팩토링
from collections import deque
def solution(bridge_length, weight, truck_weights):
    bridge = deque([0] * bridge_length)
    total_weight, time = 0, 0
    for w in truck_weights:
        while True:
            time += 1
            total_weight -= bridge.popleft()
            if total_weight + w <= weight:
                bridge.append(w)
                total_weight += w
                break
            bridge.append(0)
    return time + bridge_length

⚡️ 리팩토링 코드의 개선점

1. sum(queue) 대신 total_weight 변수를 사용
   • O(N) → O(1)로 최적화
   • total_weight를 유지하면서 매번 더하지 않고 빼고 더하는 방식으로 시간 절약
2. 매번 리스트 재생성 없이 popleft() 사용하여 시간 업데이트
   • time 리스트를 따로 만들지 않고 그냥 time 변수를 직접 증가시키는 방식으로 최적화
3. while True를 사용해 한 번에 트럭을 올릴 수 있는 시점까지 반복
   • 불필요한 flag 제거 → i == len(truck_weights) 체크 없이 간결해짐
4. 마지막 트럭이 다리를 건너는 시간 추가 (time + bridge_length)
   • 트럭이 다리를 다 건너는 마지막 시간을 따로 처리하여 명확한 종료 조건 적용