[Algorithm 풀이] 다리를 지나는 트럭

프로그래머스 코딩테스트 고득점 kit (스택 / 큐)

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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_length   weight         truck_weights                                                                                               return

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

 

---

⭐️  SOLUTION

# deque 로도 풀 수 있지만 case 4번에서 시간 초과 뜸.
def solution(bridge_length, weight, truck_weights):
    time = 0
    out_bridge = []
    bridge = [0] * bridge_length
    current_weight = 0
    while bridge:
        time+=1
        truck = bridge.pop(0)
        current_weight -= truck
        
        if truck_weights:
            if (current_weight + truck_weights[0]) <= weight: 
                current_weight += truck_weights[0]
                bridge.append(truck_weights.pop(0))
            else:
                bridge.append(0)
                     
    return time

스택/ 큐를 이용하여 푸는 문제이다. deque로도 풀 수 있고, list(stack)으로도 풀 수 있는 문제이다.

요 문제의 포인트는 다리 위의 트럭이 없을 때 까지 whille문을 돌리고, 넣을 트럭과 이미 다리위에 있는 트럭들의 합이 다리 제한 중량을 초과할 경우 0을 넣어줘서 다리의 길이를 유지해주는 것이다.

이해를 위해 첫번째 예시를 표로 만들면, 다음과 같다. bridge 가 빌 때까지 while 문을 돌리자!

time	bridge	truck_weight
Init	[0, 0]	[7, 4, 5, 6]
1	[0, 7]	[4, 5, 6]
2	[7, 0]	[4, 5, 6]
3	[0, 4]	[5, 6]
4	[4, 5] (합이 10 이하이기 때문)	[6]
5	[5, 0]	[6]
6	[0, 6]	[ ]
7	[6]	[ ]
8 (종료)	[ ]	[ ]

 

* 런타임 에러 기록

첨에 weight 비교 부분에서 sum(bridge)의 합과 하나 뺄 truck_weight[0]와의 합으로 계산했는데 sum()연산은 O(2n)이 걸리므로 시간 초과가 남!!!!!!! 그래서 따로 current_weight 라는 변수를 만들어 줘서 bridge 를 올라가고 내려갈 때 더해주고 뺴주었다!

if (sum(bridge) + truck_weights[0]) <= weight: