프로그래머스 42583 다리를 지나는 트럭

다리를 지나는 트럭 문제에 대한 설명은 다음의 링크를 참고해주시기 바랍니다. 문제 설명

프로그래머스

우선, 다리를 지나는 트럭은 truck_weights로 주어진 트럭의 순서가 변경될 수 없습니다. 따라서 정해진 순서를 기반으로 모든 트럭이 다리를 건너는 최소 시간을 정답으로 구합니다.

 

예시는 자세한 설명을 동반하고 있어 질문하기 목록에 있는 예시 테스트 케이스 중 하나로 문제 해결 순서를 확인해보겠습니다. 질문하기

bridge_length = 5, weight = 5, truck_weights = [2, 2, 2, 2, 1, 1, 1, 1, 1]

 1 초 2 무게의 트럭이 들어왔다. 현재 다리의 무게 = 2
 2 초 2 무게의 트럭이 들어왔다. 현재 다리의 무게 = 4
 6 초 2 무게의 트럭이 나갔다. 현재 다리의 무게 = 2
 6 초 2 무게의 트럭이 들어왔다. 현재 다리의 무게 = 4
 7 초 2 무게의 트럭이 나갔다. 현재 다리의 무게 = 2
 7 초 2 무게의 트럭이 들어왔다. 현재 다리의 무게 = 4
 8 초 1 무게의 트럭이 들어왔다. 현재 다리의 무게 = 5
11 초 2 무게의 트럭이 나갔다. 현재 다리의 무게 = 3
11 초 1 무게의 트럭이 들어왔다. 현재 다리의 무게 = 4
12 초 1 무게의 트럭이 들어왔다. 현재 다리의 무게 = 5
13 초 2 무게의 트럭이 나갔다. 현재 다리의 무게 = 3
13 초 1 무게의 트럭이 들어왔다. 현재 다리의 무게 = 4
14 초 1 무게의 트럭이 들어왔다. 현재 다리의 무게 = 5
남은 트럭 = [1,1,1,1,1]
정답: 19초

위의 과정을 통해서 최소 시간이 결정되게 됩니다. 다음은 문제를 해결함에 있어 유의해야 할 사항입니다.

• 오직 트럭이 나간 후에 여유 무게가 있다면 같은 시간에 트럭이 들어올 수 있다. 
• 모든 트럭이 다리에 올라간 상태라면 현재 시간에 bridge_length를 더해주면 최소 시간이 된다.

첫 번째는 같은 시간에 처리될 수 있는 경우는 트럭이 나갔을 때 들어오는 경우뿐이라는 것입니다. 여유 공간이 있어 트럭이 들어온 후에 나가는 경우는 현재 시간에 +1을 한 후에 처리해야 합니다. (테스트 케이스 4,5,6,9번을 틀렸다면 이 부분을 주의 깊게 봐야 한다)

 

두 번째는 모든 트럭이 다리에 올라갔다면 얼마가 남았든 상관없이 현재 시간에 bridge_length를 더해주면 됩니다. 왜냐하면 현재 시간은 마지막 트럭이 다리에 올라간 시간이므로 마지막 트럭이 다리를 빠져나갔다면 다른 트럭들도 빠져나갔을 것이기 때문입니다.

 

두 가지 유의사항에 만족하며 코드를 작성하면 다음과 같습니다.

def solution(bridge_length, weight, truck_weights):
    queue = []
    answer, current_weight = 0, 0

    while truck_weights:
        if current_weight + truck_weights[0] <= weight:
            truck = truck_weights.pop(0)
            current_weight += truck
            queue.append((answer, truck))
            answer += 1
        else:
            time, truck = queue.pop(0)
            current_weight -= truck
            answer = max(answer, time + bridge_length)
    return answer if not queue else answer + bridge_length

모든 트럭이 다리에 올라가기 전까지 반복문을 돌면서 여유 무게가 있다면 트럭을 다리에 올리고 아니라면 가장 오랫동안 머무른 트럭을 지나가게 만들어주는 과정을 반복합니다.

 

해당 문제는 큐를 중심으로 문제를 해결할 수 있습니다. 트럭을 처리하는 순서, answer를 초기화해주는 시점 등 여러 조건들이 처리되므로 문제의 논리를 어떤 순서로 처리해줄 것인지 생각하는 것이 더 중요한 문제였습니다.