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

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

문제 설명

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

입출력 예시

풀이 과정

스택과 큐 범주에 있는 문제 였는데 내가 생각하기엔 ? truck에서 젤 왼쪽부터 차례대로 트럭이 이동하게 되므로 deque를 쓰면 좋을 것 같다고 생각했다.

- 다리길이만큼 지나야하는 것을 어떻게 구현할 것인가 !?

현재 다리를 지나고 있는 중인 트럭들을 담기 위한 tmp_truck이라는 deque를 만들었다. 처음에는 다리의 길이를 생각하지 않고 구현하여 테스트케이스를 많이 틀렸었다. 다리 길이만큼 truck이 지나야하므로 이걸 어떻게 검사해야할까 고민하던 중 다른 사람들의 코드를 보게되었다. 이때 얻게된 힌트는 tmp_truck을 빈 큐가 아닌 0으로 채워진 다리 길이만큼의 큐로 만드는 것이였다. 

- sum()의 시간초과 문제

sum()을 사용하여 현재 다리를 지나는 중인 트럭들의 합을 구했다. 테스트 케이스 5번에서 계속 시간초과가 나서 질문을 찾아보니 sum()을 사용하는 것은 O(N)의 시간 복잡도를 갖고있기 때문에 발생하는 문제였다. 그래서 sum을 사용하지 않고 현재 다리를 지나는 중인 트럭들의 합을 구할 수 있는 방법을 고민하다 생각해낸 방법은 그냥 tmp_truck에서 하나씩 넣거나 뺄때 sum_truck의 값도 넣거나 빼주는 방법이였다.

from collections import deque


def solution(bridge_length, weight, truck_weights):
    truck_weights = deque(truck_weights)
    tmp_truck = deque([0] * bridge_length)
    timer = 0
    sum_truck = 0
    while tmp_truck:
        timer += 1
        sum_truck -= tmp_truck.popleft()

        if truck_weights:
            if sum_truck + truck_weights[0] <= weight:
                pop_truck = truck_weights.popleft()
                tmp_truck.append(pop_truck)
                sum_truck += pop_truck
            else:
                tmp_truck.append(0)
    return timer


if __name__ == "__main__":
    print(solution(2, 10, [7, 4, 5, 6]))
    print(solution(100, 100, [10]))
    print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]))

 

 

Python, Python 백준, Python 백준 18258, python 알고리즘, Python 큐 2, 백준 18258 파이썬, 알고리즘 큐 2, 파이썬, 파이썬 백준, 파이썬 큐 2