문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
bridge_length: 다리의 길이를 나타내는 변수로, 이 값은 동시에 다리 위에 올라갈 수 있는 최대 트럭수를 의미한다. 따라서 'bridge_length'만큼의 길이를 가진 'bridge'는 다리 위에 올라간 트럭들을 나타내기 위해 사용된다.
weight: 다리가 견딜 수 있는 최대 하중을 나타내는 변수로, 이 값을 초과하는 무게의 트럭은 다리를 건너지 못합니다.
truck_weights: 트럭들의 무게가 순서대로 담긴 리스트입니다. 이 리스트는 트럭들이 건너야 할 순서를 나타냅니다.
answer: 모든 트럭들이 다리를 건너는 데 필요한 시간을 저장하는 변수로, 초기값은 0으로 설정됩니다.
bridge: 현재 다리에 올라간 트럭들을 나타내는 리스트입니다. 처음에는 길이가 bridge_length인 모든 요소가 0으로 초기화됩니다.
pop(): 리스트의 특젇 인덱스에 있는 요소를 제거하고 해당 요소를 반환하는 함수
기본적으로 pop()은 리스트의 마지막 요소를 제거하고 반환하지만, 인덱스를 지정하면 해당 인덱스의 요소를 제거하고 반환한다.
이 코드에서는 다리에 올라간 트럭들이 시간이 지나면서 다리를 건너기 때문에 가장 앞에 있는 트럭을 계속해서 제거하는 용도로 사용되었다.
- 스택 자료구조인 pop()메서드 사용
# 동시에 다리 위에 올라갈 수 있는 최대트럭수, 다리가 견딜 수 있는 최대하중의 변수 ,
# 트럭들의 무게가 순서대로 담긴 리스트를 solution 함수로 입력을 받는다.
def solution(bridge_length, weight, truck_weights):
# 모든 트럭들이 다리를 건너는데 필요한 시간을 저장하는 변수로, 초기값을 0으로 설정
answer = 0
# 현재 다리에 올라간 트럭들을 나타내는 리스트 bridge
# 처음에는 bridge_length인 모든 요소가 0으로 초기화하여 처음에는 다리가 비어있는 상태
bridge = [0 for _ in range(bridge_length)]
while bridge:
# 매 반복마다 시간을 1초씩 증가하고
# 가장 앞에 있는 트럭을 다리에서 빼내며, 즉 다리를 건넌 트럭은 리스트에서 제거된다
answer += 1
bridge.pop(0)
# 현재 다리에 올라간 트럭들과 다음으로 올라갈 트럭의 무게를 합쳐서
# 최대 하중을 초과하지 않는지 확인, 초과하지 않는 경우,
# 다음으로 올라갈 트럭은 'truck_weight' 리스트에서 꺼내서 'bridge'리스트에 추가
if truck_weights:
if sum(bridge) + truck_weights[0] <= weight:
t = truck_weights.pop(0)
bridge.append(t)
# 최대 하중을 초과하는 경우, 다음으로 올라갈 트럭대신 무게가 0인 빈공간을
# bridge 리스트에 추가. 이렇게 하면 현재 다리에 올라간 트럭들은 움직이지않는다
else:
bridge.append(0)
# 모든 트럭이 다리를 건너는데 걸린 시간인 'answer'값을 반환
return answer O(1)
