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

문제

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

---

오랫만에 알고리즘을 풀어보았다. 감을 다시 잡기 위해서 기초적인 알고리즘인 스택/큐를 풀어보았다.

제공되는 트럭들이 다리가 버틸 수 있는 무게를 초과하지 않으면서 모든 트럭이 지나갈 때까지 걸리는 시간을 구하는 문제다. 먼저 다리에 진입한 트럭이 다리를 먼저 빠져나가기 때문에 큐를 이용해서 문제를 풀기로 했다.

문제를 풀면서 좀 더 쉬운 방법이 없을까 고민고민하다가 결국 하나씩 조건을 만들어서 풀기로 결정.

코드의 흐름은 대강 다음과 같다.

 

• 시간이 1초 흐른다.
• 다리가 버틸 수 있는 무게(weight)를 초과하지 않는다면 대기중인 트럭이 다리에 진입한다.
• 다리를 지나가고 있는 트럭들의 위치(bridge_time)를 갱신한다.
• 트럭이 다리를 지나갈 경우 다리를 지나간 트럭으로(finsh) 간주한다.
• 제시된 트럭들이 다리를 다 지나갈 경우 종료한다.

까다로웠던 점은 하나의 트럭이 다리를 빠져나가면서 동시에 다리가 버티는 무게를 초과하지 않는 선에서 다음 트럭이 들어온다는 점이다.

 

---

answer = 0
truck_count = len(truck_weights)
finished = [] # 다리를 지난 트럭들을 나타내는 리스트
truck_que = deque(truck_weights)
bridge = deque([])  # 현재 다리를 건너는 중인 리스트
bridge_time = deque([]) # 트럭이 다리에 있는 시간을 나타내는 리스트

 

이번 문제에 사용한  변수들이다. 하나씩 살펴보자.

 

• answer : 모든 트럭들이 빠져나간 최종적인 시간.
• truck_count : 반복문을 종료하는 조건으로 사용될 트럭들의 개수
• finished : 다리를 지난 트럭들을 나타내는 리스트
• truck_que : 대기중인 트럭들의 que
• bridge : 다리를 건너는 중인 트럭들의 que
• bridge_time : 트럭이 다리에 있는 시간을 나타내는 리스트

 

def addTruck(truck_que,bridge,weight,bridge_time,plus):
        if truck_que and (sum(bridge)+truck_que[0]) <= weight :
            bridge.append(truck_que.popleft())
            if plus == 0 :
                bridge_time.append(0)
            else :
                bridge_time.append(1)

 

대기 중인 트럭을 다리 위에 올려 놓는 함수다. 현재 다리에 있는 트럭들의 무게( sum(bridge) )와 다리에 진입할 트럭

( truck_que[0] )의 무게가 다리가 버틸 수 있는 무게( weight )를 초과하지 않으면 bridge에 트럭을 추가함과 동시에 상황에 따라서 bridge_time에 0 또는 1을 추가한다. 0과 1의  차이는 뒤에서 설명하겠다.

 

 for i in range(len(bridge_time)) :
            bridge_time[i] += 1

 

현재 다리를 지나가고 있는 트럭들의 시간을 갱신한다.

 

if bridge_time[0] > bridge_length :
            finished.append(bridge.popleft())
            bridge_time.popleft()
            addTruck(truck_que,bridge,weight,bridge_time,1)
        
if len(finished) == truck_count :
            break

 

트럭이 다리를 빠져나갈 때를 나타내고 있다. 1초가 흐를 때마다 트럭은 1의 길이만큼 움직인다. 여기서 주의해야할 점은 다리를 완전히 빠져 나가는 시간은 다리의 길이 +1 이라는 점이다. 그림을 보면서 이해해 보도록 하자.

맨 처음 트럭이 길이가 2인 다리에 들어가기 전에 bridge_time은 0이다.

1초가 흐른 후 트럭이 다리에 들어온다. 다리에 들어온 시점에 bridge_time은 1이 된다.

다리 길이의 끝에 도착할 때는 bridge_time의 값은 다리의 길이와 같아진다.

중요한 건 이 부분이다. 다리에 끝자락에 도착한 시간은 다리의 길이와 같은 시간대지만, 트럭이 다리를 완전히 빠져나갈 때 bridge_time은 다리에 길이에서 +1을 한 값이 3이 된다.

다리를 빠져나가는 트럭은 동시에 여러 대일 수 없고, 가장 먼저 다리에 들어온 트럭이 가장 먼저 빠져나가기 때문에

조건식에서 bridge_time의 가장 앞 요소만 비교하고, 다리의 길이( bridge_length )보다 값이 더 클 경우에만 finished에 트럭을 넣어준다. 그리고 트럭이 빠져 나갔기 때문에 대기 중인 트럭이 들어올 수 있고, 진입했을 경우 bridge_time의 값은 1이 되므로 addTruck함수에 true 변수의 값을 이용해 bridge_time의 값이 1인 상태로 넣어 준다. 왜냐하면 이미 현재 다리에 존재하는 트럭들의 bridge_time 값을 갱신했기 때문이다.

트럭 A가 다리를 빠져나갔을 때 같은 시간대에 일어나는 일이기 때문에 뒤이어 들어오는 트럭 B의 bridge_time이 1인 상태다.

 

전체적인 코드는 다음과 같다.

 

from collections import deque

def addTruck(truck_que,bridge,weight,bridge_time,plus):
        if truck_que and (sum(bridge)+truck_que[0]) <= weight :
            bridge.append(truck_que.popleft())
            if plus == 0 :
                bridge_time.append(0)
            else :
                bridge_time.append(1)

def solution(bridge_length, weight, truck_weights):
    answer = 0
    truck_count = len(truck_weights)
    finished = [] # 다리를 지난 트럭들을 나타내는 리스트
    truck_que = deque(truck_weights)
    bridge = deque([])  # 현재 다리를 건너는 중인 리스트
    bridge_time = deque([]) # 트럭이 다리에 있는 시간을 나타내는 리스트
    while True :
        answer += 1
        addTruck(truck_que,bridge,weight,bridge_time,0)
        
        # 트럭들이 다리를 지나가는 시간 갱신
        for i in range(len(bridge_time)) :
            bridge_time[i] += 1
        
        # 트럭이 다리 끝에 도착했을 때
        if bridge_time[0] > bridge_length :
            finished.append(bridge.popleft())
            bridge_time.popleft()
            addTruck(truck_que,bridge,weight,bridge_time,1)
        
        if len(finished) == truck_count :
            break
        
    return answer

---

오랫만에 풀어서 많이 난잡해 보이긴 하다... 쉬운 문제여도 하루에 한 문제씩은 꼭 풀어야될 것 같다.