[프로그래머스 42583 파이썬] 다리를 지나는 트럭 (level 2, 스택/큐)

알고리즘 유형 : 큐
풀이 참고 없이 스스로 풀었나요? : O

https://programmers.co.kr/learn/courses/30/parts/12081

소스 코드(파이썬)

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    
    # 현재 다리 위 트럭들의 무게 총합
    w = 0
    
    # 다리 위 상태를 나타내는 큐
    bridge = deque()
    
    # 모든 트럭을 pop하여 다리를 건너게 할 때까지 반복
    # 한 반복 단계에서, 다리 맨 끝 트럭을 내리게하고 새로운 트럭 또는 빈공간을 다리에 올리는 것을 수행
    while truck_weights:
        # 만약 다리 위 트럭들과 빈 공간의 개수 합이 다리 길이와 같다면, 맨 마지막 트럭은 다리에서
        # 내려주고 다리 위 무게 총합 갱신
        if len(bridge) == bridge_length:
            w -= bridge.popleft()
        
        # 만약 대기 중인 1순위 트럭의 무게가 다리 위 남은 여유 무게 이하이면, 그 트럭을
        # 다리 위로 올려보낸다. 그렇지 않다면, 아무 트럭도 못 올려보내므로, 그냥 빈 공간을
        # 의미하는 0을 올려보낸다. 이 때 자연스럽게 다리 위 모든 트럭과 빈공간은 한 칸 앞으로
        # 전진하는 효과가 생긴다.
        cnt = truck_weights[0]
        if cnt <= weight - w:
            truck = truck_weights.pop(0)
            bridge.append(truck)
            w += truck
        else:
            bridge.append(0)
        answer += 1
    
    # 위 while문은 대기 중인 마지막 트럭을 다리 위에 올려보낸 후 종료된다.
    # 즉 다리의 출발 부분에 마지막 트럭이 있는 채이므로, 마지막 트럭이
    # 다리를 건너는데 걸리는 시간만큼을. 즉 다리의 길이만큼의 시간을 
    # answer에 더해주면 그게 최종 답이다.
    answer += bridge_length
    return answer

풀이 요약

1. 다리 위 트럭의 진행도와 빈 공간 등을 큐로 나타낸다.

2. 대기 중인 트럭을 모두 건너게 할 때까지 while문을 반복한다.

   각 반복 단계에서, 다리의 가장 끝 부분에 있는 트럭을 내리고(큐의 길이와 다리 최대 길이가 같다면, 이 때 다리의 가장 끝 부분에 트럭이든 빈 공간이든 무언가가 있다는 뜻이므로.),

   이 후 다리의 시작 부분에 새로운 트럭을 올린다(단, 한도 무게를 고려해서 충족한다면).

   이 때 다리는 큐로 구현했으므로, 새로운 트럭을 넣으면 나머지 트럭들은 자연스레 한 칸씩 앞으로 전진하게 된다고 생각하면 편하다.)

3. while 문은 마지막 트럭을 다리 위의 출발 지점에 올리고 끝이 나는데, 이 때는 트럭이 다리를 건너는 시간인 bridge_length만큼을 answer에 더해주면 된다.

4. 다리를 나타내는 큐 bridge를, 가로 방향이며 칸이 10개인 progress bar를 생각하면 좀 더 이해하기 편할 것 같다. 이 때 트럭과 빈 공간은 하나의 칸을 차지한다.

배운 점, 어려웠던 점

• 풀고 나서, 다른 사람의 풀이를 보고 코드를 최적화했다.

  중복 작성된 조건문을 발견하여 정리해줬고, cnt = truck_weights[0] 구문으로 pop하지 않고 조회만 해준다면, 한도 무게 조건을 충족하지 않는 경우 pop을 안해도 된다는 점을 발견하고 적용했다.