[Python]스택/큐: 다리를 지나는 트럭

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭
0[][][7,4,5,6]
1~2[][7][4,5,6]
3[7][4][5,6]
4[7][4,5][6]
5[7,4][5][6]
6~7[7,4,5][6][]
8[7,4,5,6][][]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

  • bridge_length는 1 이상 10,000 이하입니다.
  • weight는 1 이상 10,000 이하입니다.
  • truck_weights의 길이는 1 이상 10,000 이하입니다.
  • 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

bridge_lengthweighttruck_weightsreturn
210[7,4,5,6]8
100100[10]101
100100[10,10,10,10,10,10,10,10,10,10]110

내 코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    bridge = deque()
    cnt = len(truck_weights)
    bridge_weight = 0
    answer = 0
    while cnt:
        try:
            if not bridge:
                bridge_weight += truck_weights[0]
                bridge.append([truck_weights.pop(0), 0])
            elif (bridge_weight + truck_weights[0]) <= weight:
                bridge_weight += truck_weights[0]
                bridge.append([truck_weights.pop(0), 0])
        except IndexError:
            pass
        answer += 1
        for i in range(len(bridge)):
            bridge[i][1] += 1
        if bridge[0][1] == bridge_length:
            bridge_weight -= bridge[0][0]
            bridge.popleft()
            cnt -= 1
    return answer + 1
  1. 다리를 que로 놓고 지나가는 것으로 생각하였다. cnt는 while문을 돌리기 위해 트럭 전체의 수를 세고, 한 대가 지날 때마다 1씩 빼게끔 하였고, 현재 다리 중량을 0으로 먼저 선언하였다. answer은 경과시간이다.
  2. if-elif 부분은 truck_weights[0]을 불러오게했는데 이 때 truck_weights가 비어있으면 IndexError 가 나서 try-except 로 이를 해결하려 했다. 첫 번째 if는 bridge가 비어있으면 truck_weights에서 pop한 값과 0(경과 상태)를 넣고 무게를 총 무게(bridge_weight)에 더하게 했다.
    elif는 bridge에 있는 경우에 들어가는데, 다음 트럭의 무게를 더했을 때, 다리가 견딜 수 있는 하중을 초과하지않으면 bridge에 리스트를 넣게끔 했다.
  3. for 문을 돌면서 경과상태를 1씩 증가시키고, 만약 그 값이 2이면 popleft로 빼는 것을 생각했다.

이렇게 했을 때 문제점이 3번에서 설명한 과정이 붙어있어서 answer이 1씩 작게나왔다. 그래서 그 부분은 그냥 answer + 1 을 리턴하면서 해결했다.

다른 사람의 생각

def solution(bridge_length, weight, truck_weights):
    q=[0]*bridge_length
    sec=0
    while q:
        sec+=1
        q.pop(0)
        if truck_weights:
            if sum(q)+truck_weights[0]<=weight:
                q.append(truck_weights.pop(0))
            else:
                q.append(0)
    return sec

0의 갯수를 경과 상태로 놓고 while을 돌면서 경과 시간(sec)을 더하고 q에서 첫 번째 값을 빼면서 진행하며, 총 무게가 다리가 견딜 수 있는 하중을 초과하지않으면 truck_weights의 0번 원소를 q에 넣고, 그렇지 않으면 0을 q에 넣는다.
생각한 방식은 나랑 유사한 것 같은데 코드 길이가 확연히 줄어있다.

좋은 웹페이지 즐겨찾기