프로그래머스) 코딩테스트 연습 : 스택/큐 - 다리를 지나는 트럭

문제와 관련한 모든 저작권은 프로그래머스 측에 있음을 명시합니다.

 

문제 설명

 

구현 아이디어

트럭이 다리 위를 지나가는 흐름에 대해서 생각해보면, FIFO 구조를 사용하는 것이 자연스러우므로, queue 자료구조를 사용하여 구현하였다. 파이썬에서 제공하는 deque를 사용할까 하다가, 많이 복잡한 문제가 아닌 것 같아서 list를 사용해서 구현하였다.

 

truck_weights 리스트에 트럭이 남아있는 동안에, 시간을 하나 씩 늘려 가면서,

1) 현재 다리 위에 있는 트럭을 빼내거나 

2) 현재 다리 위에 있는 트럭을 한 칸씩 밀어준다.

 

동시에 새로 유입되는 트럭에 대해서 생각해야하는데,

1) 현재 다리 위의 트럭 무게에 신규 트럭 무게를 추가해도 괜찮다면, 트럭을 한 대 더 올리고

2) 추가하면 인자로 받은 weight를 초과할 경우, 트럭을 추가하지 않는다.

 

다리 위에 트럭이 한 대도 남지 않는 상황이 되면, 모든 트럭이 다리를 지나간 것이므로, while문을 종료 시킨다.

 

파이썬으로 구현시, 5번 test case 시간 초과

실제로 작동 시켜보면, 정확도 상으로 문제가 일어나진 않았지만 시간 초과로 5번이 해결되지 않았다.

 

파이썬으로 구현할 때, sum 함수 연산이 O(N)을 따르는데, 이로 인해서 시간 초과에 걸리는 것으로 추측했다.

따라서 present라는 현재 다리 위의 무게를 다루는 변수를 추가하여, sum 함수를 사용하지 않고, 

트럭을 유입시키고 내보낼 때에 적절히 변수 연산을 처리하였다. 

 

문제 풀이와 관련한 모든 저작권은 작성자에게있음을 명시합니다.

 

소스 코드

 

def solution(bridge_length, weight, truck_weights):
    time = 0

    N = len(truck_weights)

    on_bridge = [0] * bridge_length  ##brideg에 현재 올라 가 있는 트럭 큐
    ##print(on_bridge)

    present_weight = 0  ##bridge에 올라 가 있는 트럭의 무게
    cnt = 0  ##bridge에 올라 가 있는 트럭의 수

    while truck_weights:
        present = sum(on_bridge)

        while present <= weight:
            time += 1

            if on_bridge:
                out = on_bridge.pop()
                if out != 0:
                    cnt -= 1
                    present = present - out

            if truck_weights and present + truck_weights[0] <= weight:
                on_bridge.insert(0, truck_weights.pop(0))
                ##print('line24')
                ##print(on_bridge)
                present = present + on_bridge[0]
                cnt += 1

            elif truck_weights and present + truck_weights[0] > weight:
                ##print('line30')
                ##print(on_bridge)
                on_bridge.insert(0, 0)

            if cnt==0: break

    return time