문제 설명
트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 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 이하입니다.
입출력 예
| bridge_length | weight | truck_weight | return |
|---|---|---|---|
| 2 | 10 | [7, 4, 5, 6] | 8 |
| 100 | 100 | [10] | 101 |
| 100 | 100 | [10, 10, 10, 10, 10, 10, 10, 10, 10, 10] | 110 |
풀이
def solution(bridge_length, weight, truck_weights):
idx = 0
time = 0
queue = []
num_of_passed_truck = 0
while True:
time += 1
for _ in range(len(queue)):
if not bridge_length - (time - queue[0]):
queue.pop(0)
num_of_passed_truck += 1
if sum(truck_weights[num_of_passed_truck:idx + 1]) <= weight:
queue.append(time)
idx += 1
if num_of_passed_truck == len(truck_weights):
return time해결 과정
-
Queue 자료구조의 형식을 사용하면 해결할 수 있을 것이다.
모든 트럭이 1초에 1씩 움직이기 때문에 가장 먼저 다리에 진입한 트럭은 가장 먼저 다리를 건너는 구조다. 이는 FIFO의 특징을 지니는 Queue 자료구조와 비슷하다고 볼 수 있다. 또한, 다리의 진입점과 나가는 곳이 지정되어 있고, 두 지점의 방향이 한 쪽으로 향하고 있기에 Queue와 비슷하다고 볼 수 있다. -
다리를 먼저 건넌 트럭을 Queue에서 제거
우선 다리를 먼저 건넌 트럭을 Queue에서 제거한 다음, 대기 트럭이 다리를 건널 수 있는지 확인해야 한다. 그렇다면, 다리 위에 있는 트럭이 지금 다리를 다 건넜는지 어떻게 확인할 수 있을까?bridge_length - (현재 시간 - 트럭이 다리에 진입한 시간)의 값이 0이라면 다리를 다 건넜다고 볼 수 있다. 1초마다 거리 1을 이동하므로, brigde_length만큼의 길이의 다리를 건너는데 소요되는 시간은 brigde_length초기 때문이다. 그래서 Queue에는 해당 트럭이 다리에 진입한 시간을 저장한다.해당 조건을 만족하는 경우, Queue에서 dequeue를 진행하고, 다리를 건넌 트럭의 수를 저장하는 num_of_passed_truck의 값을 1 증가시킨다.
-
대기 트럭이 다리를 건널 수 있는지 확인
이후, 대기 트럭이 현재 다리를 건널 수 있는지 무게 조건을 확인해야 한다. 이 경우(지금 다리를 건너는 중인 트럭의 무게 + 자신의 트럭 무게) <= weight조건을 만족하면 해당 트럭은 다리를 건널 수 있다.어차피 트럭은
truck_weights에 들어온 순서대로 다리를 건너기 때문에 해당 배열을 사용하기로 했다. 현재 다리 위에 있는 트럭의 범위는 인덱스 번호를 기준으로num_of_passed_truck ~ idx다.이 범위 내에 있는 트럭들의 무게의 합이 weight 이하인지 확인해 조건을 통과할 때 Queue에 진입한 시간을 enqueue하고, idx 값을 1 증가시킨다.
-
모든 트럭이 다리를 건넜는지 확인
num_of_passed_truck의 값이 truck_weights의 길이와 같다면, 모든 트럭이 다리를 건넜다는 뜻이므로, 현재 시간을 저장하고 있는 time의 값을 반환한다.
다른 사람의 풀이
def solution(bridge_length, weight, truck_weights):
q=[0]*bridge_length
sec=0
while q:
sec+=1
q.pop(0)
if truck_weights:
if sum(q)+truck_weights[0]<=weight:
q.append(truck_weights.pop(0))
else:
q.append(0)
return sec기본적으로 bridge_length 길이만큼의 Queue를 생성한다. 모든 트럭이 다리를 다 건너는 경우는 최소 bridge_length초이기 때문이다. (대기 트럭이 하나인 경우)
이후 Queue에 요소가 있는 경우만 반복문을 돌면서 초마다 dequeue를 진행한다. 이후, 대기 트럭이 있다면 Queue의 합(다리를 건너는 중인 트럭들의 무게) + 대기 트럭의 무게가 weight 이하인 경우 해당 요소를 꺼내 enqueue한다. 아니라면 0을 enqueue한다.
대기 트럭이 다리를 건너지 못한 경우에도 Queue에 0을 enqueue함으로써 시간 오류가 발생하지 않게 했고, Queue의 합을 구할 때도 값에 영향이 가지 않게 설계했다.
