[Python 파이썬] 프로그래머스 - 다리를 지나는 트럭

2024년 7월 17일

문제 링크 : 프로그래머스 - 다리를 지나는 트럭

 

문제 접근

 

문제의 핵심은 다음과 같다.

 

1. 다리 위에 있는 트럭이 다리를 건널 수 있으면 건너게 하고, 이후에 다리에 트럭이 올라올 수 있으면 다리 위로 트럭을 올림

2. 다리를 건널 때, 트럭은 1초에 1만큼 이동한다고 가정하며, 다리의 길이가 n이라면 n초 후에 다리를 건너게 됨

3. 다리가 버틸 수 있는 한계무게가 존재하며, 한계무게를 넘어서는 트럭은 기다려야 함

 

 

특히, 1번의 경우가 중요하다고 생각한다.

 

문제 예시를 보면, 다리 위에 트럭이 오르고 1초마다 1씩 움직여 최종적으로 트럭이 다리를 건널 수 있다면 다리를 건너게 한 이후에 다리에 트럭을 올릴 수 있는지 확인해야 한다.

 

문제에서 제시된 예시는 다음과 같다.

 

 

이 과정을 그림으로 그려보면 다음과 같다. (가시성 좋게 그림으로 표현했을 뿐, 실제 코드는 조금 다르다)

 

time = 0

 

 

다리의 길이는 2이며, 다리가 버틸 수 있는 한계무게는 10이다.

트럭은 1초에 1만큼 이동한다.

 

time = 1

 

 

대기 트럭 중, 첫 번째 트럭은 다리에 오를 수 있다. 이는 현재 한계무게보다 무게가 작기 때문.

 

다리에 트럭을 올리고 time이 1일 때의 로직을 마무리한다.

 

 

time = 2

 

 

다리 위의 트럭이 먼저 움직이고, 대기 트럭을 다리에 올릴 수 있으면 올려야 한다.

 

 

하지만 대기 트럭 중 첫 번째 트럭의 무게가 현재 다리의 한계무게보다 무겁기에 다리에 올라설 수 없다.

 

여기까지 time이 2일 때의 로직을 마무리한다.

 

 

time = 3

 

 

다리의 트럭을 먼저 움직여준다. 현재 다리를 건너고 있는 트럭은 time이 3일 때 최종적으로 다리를 건널 수 있으므로 다리에서 다리를 지난 트럭으로 옮겨준다.

 

 

그리고, 대기 트럭 중 첫 번째 트럭이 다리에 올라올 수 있는지 확인하고 가능하다면 다리에 트럭을 올려준다.

 

 

여기까지 time이 3일 때의 로직을 마무리한다.

 

 

time = 4

 

 

 

다리 위의 트럭을 1만큼 이동시켜준다. 아직 다리를 완전히 건널 수 있는 트럭은 없다.

 

 

그리고 현재 다리의 한계무게와 비교하여 대기 트럭을 올릴 수 있는지 확인한다.

올릴 수 있으므로 다리에 트럭을 올려준다.

 

 

time이 4일 때의 로직을 마무리한다.

 

 

time = 5

 

 

 

다리 위의 트럭을 1 만큼 전진시키며, 최종적으로 다리를 건널 수 있는 트럭을 다리를 지난 트럭으로 옮겨준다.

 

 

또한 다리에 남아 있는 트럭이 있으니 1 만큼 전진시켜준다.

 

 

time이 5일 때의 로직을 마무리한다.

 

이와 같은 방법으로 대기 트럭과 다리 위에 트럭이 모두 없을 때까지, 즉 모든 트럭이 다리를 건널 때까지 반복한다.

 

 

time = 6

 

 

 

 

 

 

time = 7

 

 

 

 

time = 8

 

 

 

 

위와 같은 순서로 로직을 동작시켰기 때문에, 예제의 정답이 8이 되는 것이다.

 

대기 트럭의 첫 번째 트럭을 빼야 한다는 점, 그리고 다리를 먼저 건너는 것도 결국 다리에 먼저 들어온 트럭 순으로 빠져나오는 점에서 큐 자료구조 2개를 활용해야겠다고 판단했다.

 

또한, 1초마다 트럭을 1칸씩 전진시키면 비효율적인 코드가 되므로

트럭이 다리에 오른 시점의 시간 + 다리의 길이 = 트럭이 다리를 최종적으로 건너는 시점의 시간임에 착안하여 

트럭이 다리를 오를 수 있을 때, 1차원 배열인 [트럭의 무게, 트럭이 다리를 최종적으로 건너는 시점의 시간]  을 배열에 append하도록 하였다.

---

전체 코드

 

from collections import deque

def solution(bridge_length, weight, truck_weights):
    truck_queue = deque(truck_weights)
    bridge_queue = deque()
    # 현재 다리 위에 존재하는 트럭의 개수
    nowTruckOnBridge = 0
    # 현재 다리가 지탱할 수 있는 무게
    nowWeight = weight
    complete = []

    time = 0

    '''
    1. 다리를 지날 수 있는 트럭이 있으면 다리를 지나게 함
    2. 다리에 트럭을 올릴 수 있으면 올림
    '''
    while truck_queue or bridge_queue:
        time += 1
        # 다리를 지날 수 있는 트럭이 있으면 다리를 지나게 함
        if bridge_queue and time == bridge_queue[0][1]:
            complete.append(bridge_queue.popleft())
            nowWeight += complete[-1][0]
            nowTruckOnBridge -= 1


        if nowTruckOnBridge < bridge_length:
            # 다리에 트럭을 올릴 수 있는 조건 : 현재 다리가 버틸 수 있는 무게의 트럭이 있어야 하고, 다리가 포화상태가 아니어야 함.
            if truck_queue and nowWeight >= truck_queue[0]:
                bridge_queue.append([truck_queue.popleft(), time + bridge_length])
                # 다리가 버틸 수 있는 무게 갱신
                nowWeight -= bridge_queue[-1][0]
                nowTruckOnBridge += 1

    return time

if __name__ == "__main__":
    bridge_length = 2
    weight = 10
    truck_weights = [7,4,5,6]

    print(solution(bridge_length, weight, truck_weights))

---

풀이 후기

 

로직 순서를 꼼꼼히 고려해야하는 문제였다.