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

programmers.co.kr/learn/courses/30/lessons/42583

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

* 시뮬레이션 문제는 확실히 디버깅을 할 때, 노트에 직접 시뮬레이션 돌려가며 하거나

   컴퓨터에 1초마다 결과값을 출력해가며 비교해야해서 오래걸리는 것 같다.

 

# bridge_length: 다리길이, weight: 다리가 최대 견딜 수 있는 무게, 

   truck_weights: 대기트럭, bridge: 현재 다리에 있는 트럭 상태이다.

 

# 원래 10~16번째 줄을 하나의 for문에서 i[1]을 증가시키고 바로 확인해서 pop(0)을 하도록 코드를 짰는데,

   pop(0)을 하는 순간 맨 앞 원소가 지워짐과 동시에 모든 원소가 한칸씩 앞으로 땡겨지는 것을 간과했다.

   여기서 시간을 많이 잡아먹었다..

 

# 14번째 줄에서 pop(0)을 해주는 이유: bridge는 Queue구조로서 선입선출이기 때문에

   시간을 1씩 증가시켰을 때 경과시간이 bridge_length에 먼저 도달하는 것은 맨 첫번째 원소일 수 밖에

   없다. 또한, 한번에 트럭이 하나씩 다리에 올라가므로 첫번째 원소만 pop해주면 된다.

from collections import deque
def solution(bridge_length, weight, truck_weights):
    # 1초일 때 첫 트럭 bridge에 넣고 time = 1 초기화
    time = 1
    bridge = [truck_weights.pop(0), 0]
    while truck_weights:
        time += 1
        
        # bridge를 돌며 안에 있는 트럭의 시간을 1씩 증가
        for i in bridge:
            i[1] += 1
            
        # bridge 안에 있는 트럭 중 경과 시간이 bridge_length이면 다리를 지난 것이므로 pop(0) 해준다.
        for i in bridge:
            if i[1] == bridge_length:
                bridge.pop(0)
                
        # bridge에 있는 트럭의 무게의 합과 첫번째 대기트럭의 무게가 weight이하이면 bridge에 대기 트럭을 append해주고
        # 대기 트럭에서 pop(0)을 해준다.
        if sum(x[0] for x in bridge) + truck_weights[0] <= weight:
            bridge.append([truck_weights.pop(0), 0])   
    
    # while문을 대기트럭이 존재하는 동안 돌렸으므로 마지막 대기트럭이 다리에 올라오는 순간 while문은 끝난다.
    # 따라서 마지막 트럭이 다리를 건너는 시간을 time에 더해주고 return해준다.
    time += bridge_length - min(x[1] for x in bridge)
    return time

(프로그래머스 level: 2)

 

# deque를 사용하면 pop(0)을 O(1)에 할 수 있으므로 더 빠르게 코드를 수행할 수 있다.

   (pop(0)으로도 통과가 되어서 그냥 deque를 사용하지 않았다.)