[프로그래머스/Lv2] 다리를 지나는 트럭

https://school.programmers.co.kr/learn/courses/30/lessons/42583#

프로그래머스

 

 

코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque([0 for _ in range(bridge_length)])
    truck_weights = deque(truck_weights)

    i = 0
    check = True
    sum_bridge = sum(bridge)
    while check:
        try:     
            if sum_bridge + truck_weights[0] <= weight:
                sum_bridge -= bridge.popleft()
                truck = truck_weights.popleft()
                bridge.append(truck)
                sum_bridge += truck
            else:
                if bridge[0] > 0:
                    sum_bridge -= bridge.popleft()
                    if sum_bridge + truck_weights[0] <= weight:
                        truck = truck_weights.popleft()
                        bridge.append(truck)
                        sum_bridge += truck
                    else:
                        bridge.append(0)
                else:
                    bridge.popleft()
                    bridge.append(0)
        except:
            if bridge[0] > 0:
                sum_bridge -= bridge.popleft()
                bridge.append(0)
            else:
                bridge.popleft()
                bridge.append(0)  

        if sum_bridge == 0:
            check = False
        
        i += 1

    return i

 

 

설명

문제가 약간 이상하게 느껴질 수 있는데 트럭들의 속도를 1초당 1칸이라고 생각하면 어느정도 이해될 것이다.

 

문제에서 예시로 보여준 과정 그대로 구현했다.

그래서 그런지 코드가 지저분한데, 설명만 참고하고 코드는 다른 사람들의 풀이를 참고하는 것을 추천한다.

 

우선 트럭들이 지나가는 다리를 만들 것이다.

bridge_length만큼의 길이를 가지는 0으로 초기화된 배열을 만든다.

 

이 다리에 트럭들을 올려놓을 것이다.

truck_weights의 원소들을 꺼내며 반복하는데

만약 다리가 받는 무게가 weight보다 작다면 트럭을 올려 놓는다

그렇지 않다면 다리에 있는 트럭을 한 칸 앞으로 옮긴다.

 

위 과정을 truck_weights의 원소가 없고 다리에도 트럭이 없을 때 까지 반복한다.

 

from collections import deque

bridge = deque([0 for _ in range(bridge_length)])
truck_weights = deque(truck_weights)

bridge_length의 길이만큼 0을 초기화하여 리스트를 만든 다음 deque로 변환하여 bridge 변수에 저장한다.

truck_weights도 deque로 변환해준다.

 

i = 0
check = True
sum_bridge = sum(bridge)

i는 시간을 기록할 변수이다.

check는 while 반복문의 조건을 담당하는 변수이다.

sum_bridge는 다리가 받고 있는 무게를 기록할 변수이다.

 

만약 while 반복문 안에서 sum() 함수를 통해 다리의 무게를 비교하면 시간초과가 발생한다.

while 반복문 바깥에서 변수로 지정해서 while 반복문 안쪽에서는 연산만하도록 하자.

 

try:     
    if sum_bridge + truck_weights[0] <= weight:
        sum_bridge -= bridge.popleft()
        truck = truck_weights.popleft()
        bridge.append(truck)
        sum_bridge += truck
    else:
        if bridge[0] > 0:
            sum_bridge -= bridge.popleft()
            if sum_bridge + truck_weights[0] <= weight:
                truck = truck_weights.popleft()
                bridge.append(truck)
                sum_bridge += truck
            else:
                bridge.append(0)
        else:
            bridge.popleft()
            bridge.append(0)

while 반복문 안쪽의 try 문이다.

여기서 try, except문의 분기 조건은 truck_weights의 원소가 없는 경우이다.

 

if sum_bridge + truck_weights[0] <= weight:
    sum_bridge -= bridge.popleft()
    truck = truck_weights.popleft()
    bridge.append(truck)
    sum_bridge += truck

만약 sum_bridge에 truck_weights[0](대기 중인 첫번째 트럭의 무게)을 더한 값이 weight보다 작거나 같다면 다리에 트럭이 올라갈 수 있다는 뜻이다.

bridge.popleft()를 사용해 다리에 있는 블록들을 한 칸씩 앞으로 당겨준다.

그리고 sum_bridge에 pop한 값을 빼준다.

truck_weights에서도 popleft()하여 대기중인 트럭 하나를 빼준다.

이 트럭을 bridge에 append한다.

다리에 트럭이 추가됐기 때문에 sum_bridge에 트럭의 무게를 더해준다.

 

else:
    if bridge[0] > 0:
        sum_bridge -= bridge.popleft()
        if sum_bridge + truck_weights[0] <= weight:
            truck = truck_weights.popleft()
            bridge.append(truck)
            sum_bridge += truck
        else:
            bridge.append(0)
    else:
        bridge.popleft()
        bridge.append(0)

만약 다리에 트럭이 더이상 못올라가면 두가지 경우에 따라 다르게 동작하도록 한다.

1. 한 번만 움직이면 다리를 건너는 트럭이 있다

2. 그렇지 않다

 

첫번째 경우에는

우선 bridge.popleft()로 다리에 있는 블록을 한 칸 앞으로 당긴다.

트럭이 다리를 건넜기 때문에 sum_bridge에서 건넌 트럭의 무게만큼 빼준다.

그 후에 sum_bridge와 truck_weights[0](대기 중인 트럭의 무게)를 더해 weight보다 작거나 같은지 비교한다.

만약 그렇다면 다리에 트럭을 올려준다.

그렇지 않다면 다리를 한 칸 앞으로 당긴다.

 

두번째 경우에는

다리를 한 칸 앞으로 당긴 후에 0(블록)을 bridge에 append한다.

 

except:
    if bridge[0] > 0:
        sum_bridge -= bridge.popleft()
        bridge.append(0)
    else:
        bridge.popleft()
        bridge.append(0)

except문으로 빠진 경우

다리에 남은 트럭들을 건너게하기 위해 동작한다.

 

만약 다리를 곧 건너는 트럭이 있는 경우에 bridge.popleft()(트럭이 다리를 건넘)하고 sum_bridge에 그 트럭의 무게만큼을 빼준다. 그 뒤에 0(블록)을 bridge에 append한다.

 

그렇지 않다면 트럭이 다리를 건너게 하고 0을 bridge에 append한다.

 

if sum_bridge == 0:
    check = False

위 동작들이 끝났을 때 sum_bridge가 0이라면(다리에 트럭이 아예 없다면) check를 False로 바꿔 while 반복문이 멈추게 한다.

 

i += 1

i를 1 더해준다.

1초가 지난 것을 의미한다.

 

return i

i를 반환한다.