Programmers. 다리를 지나는 트럭

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 다리를 지나는 트럭

문제 풀이

처음엔 시간복잡도를 생각해 다리 무게와 트럭의 진입, 퇴장 시기를 고려하여 적절히 더하면 되겠다 싶었는데 연산이 너무 이상하게 꼬였다. 다른 풀이를 보니 정말 정직하게 큐를 이용해서 1개씩 count를 하고 있었다. 생각해보니 전체 탐색해봐야 $10^9$으로 대략 1초가 걸려 Python으로 TLE가 걸리지는 않을 것 같았다. 연산이 괜히 복잡해지면 완전 탐색도 고려할 법하다.

이 문제의 핵심은 다리를 0으로 가득 채워진 큐로 선언해서 해결한다는 점이었다.

• 도착한 트럭 개수를 저장할 변수 선언
• 매 탐색마다 다리에서 popleft된 값이 0보다 크면 트럭이므로 현재 적재된 무게에서 빼고 도착한 트럭 대수를 1 더한다.
• 만약 아직 적재할 트럭이 남아있고 맨 앞 트럭 + 현재 적재된 무게가 다리의 용량 이하라면 트럭이 진입해도 되므로 다리에 넣는다.
• 그렇지 않은 경우 기존 적재된 트럭만 전진해야 하므로 0을 넣는다.
• 시간 카운트 + 1

python 코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    N = len(truck_weights)
    b_weight, arrived = 0, 0
    q = deque([0] * N)
    answer = 0
    while arrived < N:
        exit = q.popleft()
        if truck_weights and truck_weights[0] + b_weight <= weight:
            truck = truck_weights.pop(0)
            b_weight += truck
            q.append(truck)
        else:
            q.append(0)
        answer += 1
    return answer