본문 바로가기
코딩테스트/프로그래머스

[프로그래머스] LV2 다리를 지나는 트럭 | 파이썬

by 애플파ol 2025. 5. 7.

Solution :

1. Stack 풀이 :

## 스택

def solution(bridge_length, weight, truck_weights):
    # 초기화
    time = 0 
    bridge=[0]*bridge_length # 다리
    weight_sum=0
    
    # 트럭이 빌 때까지 반복문 돌림.
    while truck_weights:
        weight_sum=weight_sum-bridge.pop(0)
        time+=1
        if weight_sum + truck_weights[0] <= weight : # weight 이하라면
            first_truck=truck_weights.pop(0) # 첫번째 트럭 
            bridge.append(first_truck) # 다리위에 추가. 
            weight_sum+=first_truck
            # print('1 :',bridge, time)
        else:
            bridge.append(0) # 다리위에 추가. 
            # print('2 :',bridge, time)   
    
    return time+len(bridge) # 마지막에 올라온 트럭은 while 문에 진입하지 못함으로, 길이만큼 초가 필요함.

 

 

2. queue 풀이 :

## 큐

from collections import deque
def solution(bridge_length, weight, truck_weights):
    # 초기화
    time = 0 
    bridge=[0]*bridge_length # 다리
    q_bridge=deque(bridge) # q_다리
    q_truck_weights=deque(truck_weights) # q_트럭무게
    current_weight = 0 
    
    # 트럭이 빌 때까지 반복문 돌림.
    while q_truck_weights:
        first_truck=q_truck_weights[0]
        current_weight = current_weight-q_bridge.popleft() # 다리에서 맨 앞칸을 제외한 무게.
        
        # 새롭게 트럭을 추가 유무
        if current_weight + first_truck <= weight : # 기존무게 + 새로운 트럭무게 <= weight 라면
            first_truck = q_truck_weights.popleft() # 첫번째 트럭을 추가함 
            q_bridge.append(first_truck) # 다리위에 추가. 
            current_weight+=first_truck
            time+=1
            # print('1 :',q_bridge, time)
        else:
            q_bridge.append(0) # 다리위에 추가. 
            time+=1
            # print('2 :',q_bridge, time)
            
    return time+len(q_bridge)

 

 

Skills :

  1. current_weight 가 필요함 :
    - 만약 아래와 같이 sum 함수를 사용한다면, 시간초과가 발생. ( 최악의 경우에 while문도 10⁴ 이고 sum도 10⁴ 임으로 -> 10⁸ 이 됨으로 시간초과.
    while q_truck_weights:
        first_truck=q_truck_weights[0]
        weight_bridge =sum(q_bridge) # while 이랑, sum 하면 10000*10000 = 10^8 이라 에러남. (10^7 까지 안전.)
        weight_bridge = weight_bridge-q_bridge.popleft() # 다리의 첫번째 부분이 나갔음.
        
        # 새롭게 트럭을 추가 유무
        if first_truck + weight_bridge <= weight : # weight 이하라면