복습은 학습한 내용을 단기 기억에서 장기 기억으로 전환하여 기억력을 극대화하고, 지식의 활용도를 높여준다.
시스터디 또한 이러한 학습 효과를 경험하기 위해 1주일 동안 복습하는 시간도 가져보기로 했다.

---

문제

오늘 복습해 볼 문제는 2월에 과제로 받았던 다리를 지나는 트럭이다.
링크

문제 요약

다리의 길이와 무게를 기준으로 두고 모든 트럭이 다리를 건너려면 최소 몇 초가 필요한지 구한다.

##  예시 ## 

# bridge_length=2, weight=10, truck_weights=[7,4,5,6]
# 초기큐 : queue=[0,0], truck_weights =[7,4,5,6], total=0
# 1초: queue=[0,7], truck_weights[4,5,6], total=7
# 2초: queue=[7,0], truck_weights=[4,5,6], total=7 (4는 무게초과로 대기)
# 3초: queue=[0,4], truck_weights=[5,6], total=4```

---

이전 풀이

from collections import deque
def solution(bridge_length, weight, truck_weights):
    # 다리를 나타내는 큐 (다리 길이만큼 0으로 초기화 - 0은 빈 공간)
    queue = deque([0] * bridge_length)
    
    # 대기 중인 트럭들을 큐로 관리
    orders = deque(truck_weights)
    
    # 경과 시간
    time = 0
    
    # 현재 다리 위에 있는 트럭들의 총 무게
    total = 0
    
    # 1. 대기 중인 트럭이 없어질 때까지 1초씩 시뮬레이션
    while orders:
        time += 1
        
        # 2. 1초가 지났으므로 다리 위 모든 트럭이 한 칸 앞으로 이동
        #    맨 앞 칸(queue[0])이 다리를 완전히 벗어나므로 총 무게에서 제거
        total -= queue[0]
        queue.popleft()
        
        # 3. 대기 중인 첫 번째 트럭이 다리에 올라갈 수 있는지 확인
        #    현재 다리 위 총 무게 + 다음 트럭 무게가 제한 무게를 초과하면
        #    트럭을 올리지 않고 빈 공간(0)으로 채워 다리 길이를 유지
        if total + orders[0] > weight:
            queue.append(0)
        else:
            # 4. 무게 제한 이하이면 대기 트럭을 다리에 올림
            #    대기 큐에서 트럭을 꺼내 다리 큐에 추가하고 총 무게 갱신
            w = orders.popleft()
            total += w
            queue.append(w)

    # 마지막 트럭이 다리를 완전히 건너는 시간 추가
    return time + bridge_length

---

새 풀이

큐에 0을 넣지 않아도 풀 수 있다.

이전 코드는 트럭이 다리에 올라가지 못할 때 deque에 0을 넣고, 올라갈 수 있을 때까지 반복했다.

그러나 트럭이 다리에 올라갈 때마다 무게, 나가는 시간을 저장한다면 불필요한 반복 연산시간을 줄일 수 있을 것이다.

예상되는 효과는 아래와 같다.

(1) 대기 시간을 매 루프마다 소비하지 않고 앞 트럭이 나가는 시간으로 바로 점프해 불필요한 반복을 제거할 수 있다

(2) 나가는 시간이 미리 저장되어 있어 마지막에 time + bridge_length 를 별도로 계산하지 않고 바로 반환할 수 있다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    # 빈 큐로 시작 - 0으로 채울 필요 없이 (무게, 나가는 시간)으로 관리
    bridge_queue = deque()

    # 대기 중인 트럭들 관리
    waiting_trucks = deque(truck_weights)

    # 현재 시간
    current_time = 0

    # 현재 다리 위 총 무게
    current_weight = 0

    while waiting_trucks or bridge_queue:

        # 1. 나가는 시간이 된 트럭만 골라서 제거
        while bridge_queue and bridge_queue[0][1] <= current_time:
            current_weight -= bridge_queue.popleft()[0]

        # 2. 다음 트럭을 올려도 무게 제한을 넘지 않는 경우
        if waiting_trucks and current_weight + waiting_trucks[0] <= weight:

            # 대기 트럭 꺼내기
            truck_weight = waiting_trucks.popleft()

            # 현재 다리 무게 증가
            current_weight += truck_weight

            # 트럭이 다리에 올라가는 시간

            # 3. (무게, 나가는 시간)을 함께 저장
            # 나가는 시간 = 현재 시간 + 다리 길이
            bridge_queue.append(
                (truck_weight, current_time + bridge_length)
            )

        else:
            # 4. 다음 트럭을 못 올리는 경우

            # 1초씩 자연 진행
            current_time += 1

            continue

        # 트럭 올린 경우에도 1초 진행
        current_time += 1

    # 마지막으로 저장했던 트럭이 다리를 완전히 건너는 시간 출력
    return current_time

---

주요 자료구조

deque

# <파이썬 알고리즘 인터뷰> p.266, 책만, 2020

일반적인 큐는 뒤에서만 삽입이 이루어지고 앞에서만 인출이 가능한 반면, 데크(Deque)는 양쪽에서 모두 삽입과 삭제가 가능해 스택과 큐의 특징을 모두 갖고 있다.

물론 이 문제에서 양쪽 삽입과 삭제를 활용하지는 않았지만, 일반적인 리스트의 삭제 연산인 pop(0)보다 popleft()가 빠르기에 성능 최적화에 도움이 되었다.

---

pop(0) vs popleft()

# list.pop(0) → O(n)
lst = [1, 2, 3, 4, 5]
lst.pop(0)
# [1, 2, 3, 4, 5]
#  ↑ 제거
# [2, 3, 4, 5]
#  ↑ ↑ ↑ ↑ 나머지 요소를 전부 한 칸씩 앞으로 당김 → 요소 수만큼 연산 발생

# deque.popleft() → O(1)
from collections import deque
dq = deque([1, 2, 3, 4, 5])
dq.popleft()
# [1, 2, 3, 4, 5]
#  ↑ 제거
#     ↑ 포인터만 다음 요소로 이동 → 요소 수와 무관하게 연산 1번

---