스택/큐 연습문제: 다리를 지나는 트럭

문제

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

weight = 10

truck_weights = [7,4,5,6]

return = 8

나의 풀이

def solution(bridge_length, weight, truck_weights):
    answer = 0
    Q = []
    while truck_weights:
        if len(Q) < bridge_length and sum(Q)+truck_weights[0] <= weight:
            Q.append(truck_weights.pop(0))
            answer+=1
        elif len(Q) < bridge_length and sum(Q)+truck_weights[0] > weight:
            Q.append(0)
            answer+=1
        else:
            Q.pop(0)
    return answer+bridge_length

다리를 지나는 과정이 FIFO 방식이어서 큐를 사용해야하는 문제로 보인다. 첫번째 풀이는 사실상 트럭이 지나는 과정을 일일이 비교하는 Brute Force 방식에다가 매번 sum(Q) 를 구해야하기 때문에 매우 비효율적이다. 풀이보다는 우선 문제를 이해하기 위해 코드를 작성했다.

def solution(bridge_length, weight, truck_weights):
    answer = 0
    Q = []
    while truck_weights:
        if sum(Q)+truck_weights[0] <= weight:
            Q.append(truck_weights.pop(0))
            answer+=1            
        else:
            answer += (bridge_length - len(Q))
            Q.pop(0)
    return answer+bridge_length

트럭 사이의 무게를 비교하는 것만으로 문제 해결이 가능하지 않을까 싶어서 작성한 코드. 실행시간은 0.01ms 대로 현저하게 줄어들었지만 예시 코드에서의 실행 결과와 달리 채점과정에서는 정확도가 많이 떨어졌다.

원인을 찾아봤는데 트럭이 다리를 못건너는 이유가 무게 때문인지, 길이 때문인지에 따라 계산 결과가 달라졌다. 이를 해결해보려고 했는데 하다보니 생각보다 과정이 더 복잡해서 일단 다시 첫번째 방법으로 돌아가 코드를 정리해보았다.

def solution(bridge_length, weight, truck_weights):
    answer = 0
    Q = [0] * bridge_length
    while Q:
        answer+=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 answer

반복되는 코드들을 하나로 합치고, 조건의 순서를 바꿔주었다. 여전히 실행속도는 느린편이지만 sum(Q)의 사용횟수가 줄어들어 다행히 이번에는 정확도 및 효율성 테스트를 통과했다. 찾아보니 대다수의 사람들이 이 방법으로 문제를 풀었다.

그러나 여전히 효율성을 높이고 싶어 두번째 방법에 대한 미련이 남는데, 아무리 코드 풀이를 찾아봐도 비슷한 코드가 없는 것을 보니 정확하지 않은 방법이었던 것 같다… 사실 효율적으로 문제를 풀고 싶어서 2번째 방법으로 문제를 푸는 것에 시간을 많이 들였는데 이렇게 집착하는 게 오히려 안 좋다는 생각이 든다. 한 문제에 집착해서 시간을 허비하느니 차라리 도움을 받고 빠르게 넘어가더라도 지금은 문제 유형을 많이 접해보는 것이 더 효율적일 것 같다.

알고리즘만 효율성을 추구하지 말고 공부도 효율성을 추구해보자…