[Programmers / Python / 스택 큐] - 다리를 지나는 트럭

Young·2021년 5월 24일
0

출처 https://programmers.co.kr/learn/courses/30/lessons/42583?language=python3

모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 한다.
트럭 움직임 : 1 / 1초
다리 길이 : bridge_length
다리가 견디는 무게 : weight
(트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않는다.)

나의 풀이

def solution(bridge_length, weight, truck_weights):
    count = 0
    on_bridge = []
    left_bridge = []

    while on_bridge or truck_weights:
        count += 1

        if len(on_bridge) == 0:
            on_bridge.append(truck_weights.pop(0))
            left_bridge.append(bridge_length)

        else:
            left_bridge = list(map(lambda x:x-1, left_bridge))

            if left_bridge[0]==0:
                left_bridge.pop(0)
                on_bridge.pop(0)

            for i in truck_weights:
                if sum(on_bridge) + i <= weight:
                    on_bridge.append(truck_weights.pop(0))
                    left_bridge.append(bridge_length)
                break 
                
    return count

코드 설명

on_bridge : 다리를 건너고 있는 트럭들의 각 무게
left_bridge : 다리를 건너고 있는 트럭이 완벽하게 건너기 위해 각 남은 길이
#한대씩만 or weigh 넘을 때 둘 다 break

  1. 다리 위에 트럭이 있거나 대기 트럭이 있는 동안 while 문 실행
    일단 while문에 들어간 경우 1초의 시간 부여
while on_bridge or truck_weights:
	count += 1
  1. 다리 위에 트럭이 없는 경우
  • 대기 트럭의 가장 앞 원소를 pop해준 뒤 다리를 건너는 트럭 배열에 append 해준다.
    (조건에서 모든 트럭의 무게는 1 이상 weight 이하라고 나와있기 때문에 별 다른 조건 검사 없이 그냥 pop append)
  • 방금 다리에 진입한 트럭이 다리를 완벽하게 건너기 위해 남은 길이를 계산해주기 위해 left_bridge 배열에 문제에서 주어진 다리 길이 bridge_length를 append 해준다.
        if len(on_bridge) == 0:
            on_bridge.append(truck_weights.pop(0))
            left_bridge.append(bridge_length)
  1. 다리 위에 트럭이 있는 경우
  • 일단 while문을 돌며 1초가 경과했기 때문에 left_bridge의 원소들를 각 -1씩 해준 뒤 가장 선두의 트럭이 다리를 다 건넜다면 left_bridge, on_bridge의 가장 앞 원소를 각각 pop 해준다.

  • for문을 돌면서 대기 트럭이 다리에 올라갈 수 있는지를 확인한다.
    이 때 앞의 트럭이 올라가지 못한다면 뒤에 트럭들은 확인할 필요가 없으므로 break를 통해 for문을 빠져나간다.

        else:
            left_bridge = list(map(lambda x:x-1, left_bridge))

            if left_bridge[0]==0:
                left_bridge.pop(0)
                on_bridge.pop(0)

            for i in truck_weights:
                if sum(on_bridge) + i <= weight:
                    on_bridge.append(truck_weights.pop(0))
                    left_bridge.append(bridge_length)
                break
profile
👩🏻‍💻

0개의 댓글

Powered by GraphCDN, the GraphQL CDN