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

문제

• 모든 트럭이 다리를 거너려면 최소 몇 초가 걸리는지 리턴
• 다리에는 트럭이 최대 bridge_length 대 올라갈 수 있고, 다리는 weight 이하까지의 무게를 견딜 수 있다.
  • 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시한다.
• 1 <= bridge_length <= 10,000
• 1 <= weight <= 10,000
• 1 <= truck 개수 <= 10,000

 

풀이

• 시간 복잡도 : 트럭 개수가 10000개 이므로 $O(N^2)$은 안된다.
• 하나의 트럭이 다리를 지나는데 bridge_length 만큼의 시간이 걸린다.
  • 큐를 bridge_length 만큼 0으로 채운다. (비어있는 다리) 
  • 이때, 동시에 트럭이 올라갈 수 있다면 함께 이동한다.
  • 트럭이 이동할 수 없다면, 0을 넣자.

 

의문점

• 최악의 경우, 하나 트럭 지나는데 10000 번 반복해야 하므로 10000*10000 으로 시간초과가 나야한다.
• 테스트 케이스에 최악의 케이스가 없나 보다..

 

from collections import deque

def solution(bridge_length, weight, truck_weights):
    truck_weights = deque(truck_weights)
    time = 0                            # 시간
    bridge = deque([0]*bridge_length)   # 다리 위 차량 현황
    bridge_weight = 0                   # 현재 다리 위 무게
    # 모든 트럭이 다리를 지날 때까지
    while truck_weights:
        time += 1                       # tick tok
        # 맨 앞의 차량 지나가고,
        bridge_weight -= bridge.popleft()                
        # 차량이 다리 위로 올라올 수 있으면 올라오기
        now = truck_weights.popleft()
        if bridge_weight + now  <= weight :
            bridge.append(now)
            bridge_weight += now
        else:
            bridge.append(0)
            truck_weights.appendleft(now)
    
    # 다리 위에 남은 트럭 마저 나오기
    while bridge:
        time += 1
        bridge.popleft()
    
    return time

 

 

풀이 2

• 위와 방식은 같은데 코드가 더 깔끔하다.

from collections import deque
def solution(bridge_length, weight, truck_weights):
    
    truck_on_bridge = deque([0]*bridge_length)   # 현재 다리 위 트럭 리스트
    time = 0        # 시간
    now_t = 0       # 현재 다리 위 트럭 무게
    # 다리 위 모든 트럭이 지나갈 때까지
    while truck_on_bridge:
        time += 1   # tick tok
        # 맨 앞의 차량 지나가고,
        now_t -= truck_on_bridge.popleft()
        
        # 차량이 남아 있다면
        if truck_weights :
            # 차량이 다리 위로 올라갈 수 있다면 올라가기   
            if now_t + truck_weights[0] <= weight :
                now_t += truck_weights[0]
                truck_on_bridge.append(truck_weights.pop(0))
            else:
                truck_on_bridge.append(0)
                         
    return time

 

References

• 프로그래머스 고득점 Kit 스택/큐