[프로그래머스] 다리를 지나는 트럭 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 큐 자료구조를 활용하여 트럭이 모두 건너는 최소 시간을 구하는 문제이다.

deque 자료구조를 사용하여 다리의 각 칸을 만들어주고 트럭을 한 칸씩 이동하도록 구현하였다.

이때 매번 다리 위 전체 무게를 sum() 함수로 계산하면 많은 시간이 소요되므로 다리 위 전체 무게를 저장할 변수를 생성해 따로 계산해 주었다.

트럭을 다리 위로 올릴 수 있으면 출발시키고, 그렇지 않다면 앞으로 이동시키고 남은 칸은 0으로 채운다.

 

1. deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
2. 다리의 길이만큼 0으로 채운 deque 자료를 만든다. bridge = deque(list(0 for _ in range(bride_length)))
3. 트럭의 무게 리스트를 deque 자료로 만들고 마지막에 0을 추가한다. truck_weights = deque(truck_weights + [0])
4. 다음에 다리 위로 올라갈 트럭의 무게를 저장한다. truck = truck_weights.popleft()
5. sum() 함수를 사용하면 시간이 많이 소요되므로 현재 다리 위 트럭 무게의 총합을 저장할 변수를 생성한다. total = 0
6. 다음에 다리 위로 올라갈 트럭의 무게가 마지막 0이 아니면 반복한다. while (truck != 0)
7. 전체 다리 위 무게에서 가장 앞 칸을 제거하고 해당 무게를 뺀다. total -= bridge.pop()
8. 만약 현재 다리 위 상태에서 다음 트럭을 출발시킬 수 있으면 if (total + truck <= weight)
9. 다리에 트럭을 출발시킨다. bridge.appendleft(truck)
10. 트럭이 다리 위로 올라갔으므로 전체 무게에 트럭 무게를 추가한다. total += truck
11. 트럭이 다리 위로 올라갔으므로 다음으로 올릴 트럭을 다시 가져온다. truck = truck_weights.popleft()
12. 반면에 트럭을 다리 위로 올릴 수 없으면 else
13. 앞으로 한 칸씩 이동해야 하므로 그냥 0을 추가한다. bridge.appendleft(0)
14. 한 번 반복문이 수행될 때마다 시간을 1초씩 증가시킨다. answer += 1
15. 마지막 트럭이 출발되면 반복문이 종료되는데, 이후 다리 위 무게가 0이 될 때까지 반복하며 while (total != 0)
16. 앞으로 옮겨지는 다리 위 무게를 계속적으로 전체 무게에서 제거하고 total -= bridge.pop()
17. 시간도 1초씩 증가시킨다. answer += 1

반응형

3. 소스코드

from collections import deque

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

    truck = truck_weights.popleft()
    total = 0
    while (truck != 0):
        total -= bridge.pop()

        if (total + truck <= weight):
            bridge.appendleft(truck)
            total += truck
            truck = truck_weights.popleft()
        else:
            bridge.appendleft(0)

        answer += 1

    while (total != 0):
        total -= bridge.pop()
        answer += 1
    
    return answer