[프로그래머스] Python 다리를 지나는 트럭 Level2 - 스택/큐

문제 바로가기

직관적으로 보기

그림으로 그려보는 것이 가장 이해가 빠르다.

이런식으로 지나간다고 생각해 보자.

1초

2초

3초

이런 형태일 것이다.

1. 다리 길이만큼의 배열을 생성해주어 다리를 만든다.
2. 다리에 있는 트럭과 다음으로 올 트럭의 합이 용량을 초과하면 다리에 있는 트럭은 지나가고 아니면 다음 트럭이 다리에 올라온다.

접근 방법

초기화
1) 다리 배열 생성
2) 트럭 배열 deque로 변환
3) 시간 초기화
4) 무게 재는 변수 초기화

• 오른쪽에서 왼쪽으로 지나가는 것이기 때문에 deque를 사용하여 popeleft 가 더 쉬울 것이다.

1. 트럭 배열에 있는 모든 트럭이 빠져나갈 때 까지 반복
   1) 시간 증가
   2) 현재 무게 계산()
   3) 현재 무게 + 트럭 첫 번째 배열 <= 용량
   • 용량 증가
   • 다리에 추가
     4) > 용량
   • 다리에0 추가
2. 시간에 다리 길이만큼 추가

코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    time = 0
    truck_weights = deque(truck_weights)
    bridge = deque([0] * bridge_length)
    current_weight = 0

    # truck이 다 빠져나갈 때 까지
    while len(truck_weights) != 0:
        time += 1
        current_weight -= bridge.popleft()

        # 다리에 있는 트럭이랑 다음 트럭이랑 합이 weight 안 넘으면
        if current_weight + truck_weights[0] <= weight:
            # 몸무게 증가
            current_weight += truck_weights[0]
            # 왼쪽이동, 새로운 트럭 추가
            bridge.append(truck_weights.popleft())
        else: # 넘으면
            # 0 추가
            bridge.append(0)

    time += bridge_length # 다 빠져나갔으면 다리 길이만큼 시간 증가

    return time