Programmers 다리를 지나는 트럭

💡문제 분석 요약

• 트럭이 다리를 건너는데, 이때 (1)다리의 길이만큼만 트럭이 올라갈 수 있고, (2)weight 이하로만 트럭이 올라가야한다.
• 모든 트럭이 건너는 최소시간을 구한다.

💡알고리즘 설계

• Queue를 사용해야겠다고 생각했다.
• 문제를 풀며 찾아보니 deque를 사용하는 것이 더 범용적인 것 같아 deque를 이용하였다.

💡코드

from collections import deque
def solution(bridge_length, weight, truck_weights):

    truck_weights = deque(truck_weights)  # truck_weights를 deque으로 변환
    onthebridge = deque([0] * bridge_length) # 다리 길이만큼 초기화하기
    time = 0
    current_bridge_weight = 0 # 현재 다리 무게

    while onthebridge: # 모든 트럭이 넘어갈 때까지 진행
        time += 1
        current_bridge_weight -= onthebridge.popleft() # 다리에서 트럭 한 대가 내려감

        if truck_weights: # 올라갈 트럭이 있다면
            if current_bridge_weight + truck_weights[0] <= weight: # 현재 다리 무게 + 올라갈 트럭의 무게
                truck = truck_weights.popleft()
                onthebridge.append(truck)
                current_bridge_weight += truck
            else:
                onthebridge.append(0)

        # 모든 트럭이 다리를 건넜으면 반복을 종료
        if not onthebridge and not truck_weights:
            break

    return time

💡시간복잡도

• while 내에는 if문만 있고 ontherbridge만 신경쓰면 되므로 O(N)일 것으로 예상된다.

💡 틀린 이유

1. 트럭을 올리는 경우, time을 증가시키는 경우는 알 것 같았는데 이것을 실제 코드로 옮기면서 언제 pop해주고, 언제 append 해줘야하는지가 애매해서 자꾸 틀렸다. 뭔가 근접했는데 자꾸 안돼서 조금 실망했다.

💡 틀린 부분 수정 or 다른 풀이

• deque를 이용해서 pop, popleft, append 등 자유롭게 사용하는 것이 더 효율적으로 보인다. 처음에는 단순 list 배열만 이용했고, 그 다음에는 queue를 import해서 썼는데 약간 애매했다. 특히 list로 했을 땐 트럭의 전진을 표시하기 위해 insert를 사용했는데 오히려 코드가 복잡해졌던 것 같다.

💡 느낀점 or 기억할정보

• deque 관련 정리하기.
• queue보다 deque가 좀 더 범용적인듯 ?