[코딩테스트] 스택/큐 - 다리를 지나는 트럭

---

문제

 

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

프로그래머스

 

 

 대기 트럭이 하나씩 차례차례로 다리를 지나서 전부 다 지나는 시간을 출력하는 문제.

 

 다리의 최대 하중이 weight로 주어지고, 1초에 길이 1씩 트럭이 전진한다고 가정하고 풀어야 한다. 이렇게 되면 마지막 트럭이 다리 위에 올라서도 그 트럭이 완전히 지나갈 때까지 시간을 세야 한다.

 

 

---

전략

 

01. 큐

 다리를 길이가 제한된 큐라고 생각하면 1초씩 트럭이 전진하다가 해당 길이만큼 이동하면 자동적으로 Out될 것이다. 따라서 매초 트럭이 올라설 수 있다면 트럭을 큐에 올려주고 아니라면 weight가 0인 정수를 올려주면 자동적으로 시간을 측정할 수 있다.

 

 

---

풀이

 

from collections import deque

def solution(bridge_length, weight, truck_weights):
    timer = 1
    bridge = deque([truck_weights[0]], maxlen=bridge_length + 1)
    wait = deque(truck_weights[1:])
    total_weight = truck_weights[0]
    
    while total_weight > 0:
        timer += 1
        bridge.append(0)
        
        if len(bridge) == bridge_length + 1 and bridge[0] != 0:
            total_weight -= bridge[0]
        
        if wait:
            nxt = wait.popleft()
            if total_weight + nxt > weight:
                wait.appendleft(nxt)
            else:
                bridge.pop()
                bridge.append(nxt)
                total_weight += nxt

    return timer

 

 collections 라이브러리의 deque함수를 이용해 다리를 나타내는 bridge 큐와 남은 트럭 배열을 하나씩 빼줄 wait 큐를 만들어 주었다. 이때 bridge의 maxlen 즉 최대 길이를 다리의 길이보다 하나를 더해서 만들어 주었는데, 그 이유는 후술할 것이다.

 

 또한 다리 위의 총 중량을 나타내기 위해 total_weight를 설정하고, 첫 타임에 트럭이 다리 위에 못 올라갈 경우는 없으니 위의 변수들을 각각 첫번째 값으로 초기화를 하고 timer를 1로 설정했다. 즉 1초에는 첫번째 트럭이 다리 위에 올라온 상태다.

 

while total_weight > 0:
    timer += 1
    bridge.append(0)

    if len(bridge) == bridge_length + 1 and bridge[0] != 0:
        total_weight -= bridge[0]

    if wait:
        nxt = wait.popleft()
        if total_weight + nxt > weight:
            wait.appendleft(nxt)
        else:
            bridge.pop()
            bridge.append(nxt)
            total_weight += nxt

 

 이제 while에서는 다리위의 총 중량이 0이 되었다면 반복문을 빠져나가도록 조건을 걸어주고, 매 순회마다 timer를 하나씩 카운트한다. 즉, while문이 1번 순회하는 것은 1초의 시간이다. 그럼 먼저 bridge에 0을 append()해서 다리 위에서 빠져나간 트럭이 있는지 체크해 총 중량을 조절해준다. 이 때 두 개의 조건을 체크하는데, 먼저 bridge[0] != 0는 bridge에서 나간 트럭이 있는지 체크하는 것이다. 이게 트럭인지 아닌지를 체크하기 위해 위에서 초기화할 때 queue의 길이를 일부러 하나 늘렸다. 두번째로 len(bridge) == bridge_length + 1 조건인데 큐가 다 차기 전에 트럭이 이미 올라와 있기 때문에 bridge[0]을 했다면 그 트럭의 중량이 출력되고 bridge[0] != 0 조건이 True가 된다. 우리는 큐가 가득 차 빠져나가는 트럭의 중량이 필요하기 때문에 큐가 다 차기 전에는 출력이 안되게끔 한 것이다.

 

 이제 if wait에서 대기 차량이 남아 있다면 그 차량을 일단 popleft()로 꺼내 nxt 변수에 담고 다리에 올라갈 수 있는지 체크한다. 만약 올라갈 수 없다면, 즉 (총 중량) + (차량 중량) > (최대 중량)이면 다시 꺼낸 nxt 변수를 wait 큐의 왼쪽에 넣어준다. 반대로 올라갈 수 있다면 아까 이 시점에 나간 트럭을 체크하기 위해 bridge 큐에 넣어줬던 0을 제거하고 대신 nxt 변수를 넣어준다. 이 시점에 트럭의 중량이 추가 되므로 total_weight에 nxt의 중량을 더해준다.

 

 이제 마지막 차량이 올라오고 났을 때 어떻게 되는지가 중요한데, if wait가 False가 되므로 bridge에 0만 계속 append되면서 차량을 1초에 한번씩 밀어낼 것이다. 그리고 결국 total_weight가 0이 되면 while문을 빠져나가고 timer를 출력하면 정답이다.