[프로그래머스] 다리를 지나는 트럭_Python level2(스택/큐)

🔒 문제

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

프로그래머스

문제 설명

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

출처

※ 공지 - 2020년 4월 06일 테스트케이스가 추가되었습니다.

---

🔓 풀이

🔑 문제 해결 / 코드

from collections import deque


def solution(bridge_length, weight, truck_weights):
    answer = 1
    truck_in_bridge = deque()
    truck_weights = deque(truck_weights)
    truck_in_bridge.append([truck_weights.popleft(), 1])
    now_weights = truck_in_bridge[0][0]
    
    while truck_in_bridge:
        if truck_in_bridge[0][1] == bridge_length:
            pop_bridge = truck_in_bridge.popleft()
            now_weights -= pop_bridge[0]

        if truck_weights:
            if now_weights + truck_weights[0] <= weight:
                truck_in_bridge.append([truck_weights.popleft(), 0])
                now_weights += truck_in_bridge[-1][0]

        for truck in truck_in_bridge:
            truck[1] += 1

        answer += 1
    return answer

---

🍀 Story

이 문제를 해결하기 위해 4가지 과정으로 분류를 해봤다.

1. 큐 자료형에 첫 번째 트럭 넣기

    - 이 과정은 첫번째 트럭이 대기열에서 이동했기에 answer 변수는 1초부터 시작하게 된다.

    - 마찬가지로 거리 1만큼 이동했기에 대기열에 있는 트럭 무게와 1을 큐 자료형에 넣어준다

    - 이때 대기열의 트럭은 popleft를 이용해 빼준다.

    - 여기서 큐 자료형은 다리를 건너는 트럭이다.

    - 다리 있는 트럭들의 무게를 구하기 위해 자료형을 반복문으로 도는 것은 비효율적이라고 생각되어 now_weights 변수를 만들어 다리에 올라가는 경우 + 연산, 빠져나가는 경우 -연산으로 현재 무게를 계속 최신화해준다.

 

# 다리를 건너는 트럭이 없을 때까지 반복하기 (반복 횟수 = x초)

2. 다리를 건너는 트럭의 거리가 다리 길이와 일치하면 큐 자료형에서 빼주기

    - 현재 무게에서 건너간 트럭의 무게 -연산

 

3. 대기열에 트럭이 있다면 현재 무게와 다음 대기열 트럭의 무게를 더해서 한도를 초과하지 않는다면 트럭이 다리 위로 올라온다.

    - 대기열 트럭에서 트럭을 빼서 다리를 건너는 트럭 큐 자료형에 넣어주기 (이때 거리는 다음 스텝에서 한 번에 올려줄 거기 때문에 0으로 입력)

    - 현재 무게 + 연산

 

4. 다리 위에 있는 트럭 이동 거리를 모두 1씩 더해준다.

 

위 논리 구조를 지나가게 되면 다리 위에 트럭이 없는 경우 현재 무게는 0이기 때문에 무조건 다음 트럭이 입장할 수 있게 되고 다리 위에 트럭이 없다는 것은 모든 트럭이 지나갔다는 것이다.

 

시간 복잡도가 O(N^2)인 2차 시간이어서 효율성이 뛰어난 코드라고는 보기 어렵다. 

고민을 해서 좀 더 효율적인 코드로 리팩토링이 가능한 부분은 보이지만 실제 코테에서 이 문제를 만나게 된다면 논리적 흐름으로 코드를 작성하는 게 가장 빨리 구현할 수 있는 부분이라고 생각했다. 

 

다리 길이가 10,000 이하인 점도 한몫했다. 

10,000^2 은 1억인데 파이썬 초단 연상이 2,500만 정도 되는 것으로 알고 있어서 최대 4~5초 정도면 테스트를 통과할 수 있다고 생각했다. 

그리고 내 로직에서는 다리 위에 올라가 있는 트럭 수가 n이기에 사실상 10,000을 제곱할 경우는 딱 하나다.

다리 길이가 10,000이고 제한 무게도 10,000 트럭 대기열의 모든 트럭 무게가 1일 때 모든 트럭이 다리 위로 올라온 경우 10,000^2 만큼 연산이 이루어진다.