https://programmers.co.kr/learn/courses/30/lessons/42583
코딩테스트 연습 - 다리를 지나는 트럭
트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이��
programmers.co.kr
문제 설명
트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 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_weights | 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 |
| 10 | 10 | [10, 10] | 21 |
| 5 | 12 | [5, 4, 3, 5, 4, 3] | 13 |
| 5 | 12 | [5, 4, 3, 5, 4, 5] | 16 |
| 5 | 12 | [5, 4, 3, 5, 4, 5, 12] | 21 |
| 5 | 12 | [5, 4, 3, 2, 3, 2, 2] | 1 |
문제 풀이
truck_weights를 순회하면서 트럭이 다리에 진입할 수 있는지 판단합니다. 판단 결과에 따라서 큐 연산(push, pop)을 수행합니다.
우선 다리는 큐를 사용해서 표현합니다.
트럭이 다리에 진입하고 나오는 과정은 FIFO입니다. 트럭의 속도가 모두 1초에 1씩 동일하기 때문에 먼저 다리에 진입한 트럭이 먼저 다리를 벗어납니다. 이러한 상황을 표현하기에 적합한 자료구조는 큐입니다. 다리를 큐라고 표현하였기 때문에 트럭이 다리에 진입하는 것은 push 연산, 트럭이 다리를 벗어나는 것은 pop 연산에 대응합니다.
그렇다면 큐에 어떠한 원소가 저장되어야 할까요? 다리를 지나는 트럭이 가지는 정보는 트럭의 무게와 다리를 벗어나기 위해서 남은 거리일 것입니다. 따라서 큐에는 (트럭의 무게, 다리를 벗어나기 위해 남은 거리)가 저장됩니다. 트럭의 이동 속도가 1초에 1 거리이기 때문에 다리를 벗어나기 위해 남은 거리는 사실상 남은 시간과 동일합니다. 따라서 큐 연산(push, pop)을 통해 무게와 시간(거리)에 대한 정보를 갱신해야 합니다.
트럭이 다리에 진입할 수 있는 경우와 그렇지 않은 경우 처리하는 연산을 자세히 살펴보아요.
트럭이 다리에 진입할 수 있는 경우는 어떻게 판단할까요? 무게를 비교하면 됩니다. 트럭에 저장된 트럭의 무게에다가 현재 대기 중인 트럭의 무게를 더했을 때 다리가 버틸 수 있는 무게(weight)인지를 확인합니다. 만약 다리가 견디는 무게에 같거나 작다면 트럭은 다리에 진입할 수 있습니다.
트럭이 다리에 진입할 수 있는지 확인하고 나서 트럭을 이동해야 합니다. 만약 대기 중인 트럭이 다리에 진입할 수 있다면 현재 다리에 있는 트럭은 1 만큼 이동(1초만큼 이동) 해서 대기 중인 트럭이 진입할 수 있는 공간을 만들어 줍니다. 하지만 대기 중인 트럭이 다리에 진입할 수 없다면 다리 가장 앞에 있는 트럭(남은 거리가 가장 짧은 트럭)은 다리에서 벗어나야 합니다. 가장 앞의 트럭이 다리에서 벗어나기 위해서는 남은 거리를 구하고 남은 거리만큼 다리에 있는 모든 트럭이 이동해야 합니다.
트럭이 이동할 때 주의해야 할 것이 있습니다. 다리에 있는 트럭이 1 만큼 이동하든 n 만큼 이동한 결과 트럭이 다리를 벗어나는 경우를 고려해야 합니다.
트럭이 이동한만큼 시간을 갱신해줍니다. 그리고 대기 중인 트럭이 다리에 진입할 수 있는지 다시 한번 확인합니다. 만약 진입 가능하다면 큐에 push 연산을 통해 이를 나타내고, 그렇지 않다면 가장 앞에 있는 트럭을 다리에서 벗어나도록 하는 과정을 반복합니다.
예시를 그림을 통해 자세히 살펴봅니다.
1 단계: 대기 중인 트럭의 무게 = 7
대기 중인 트럭의 무게가 7인 경우입니다. 현재 큐(다리)에 트럭이 없기 때문에 당연히 대기 중인 트럭은 다리에 진입할 수 있습니다.
다리(큐)에 트럭이 없기 때문에 이동할 트럭이 없습니다.
경과한 시간만 1 증가하도록 합시다.
대기 중인 트럭이 다리(큐)에 진입(push)합니다. 큐에 들어가는 원소로는 대기 중인 트럭의 무게와 트럭이 이동해야 하는 다리의 길이입니다. 특히 이동해야 하는 다리의 길이는 사실상 이동 시간과도 같음을 기억해야 합니다.
2 단계: 대기 중인 트럭의 무게 = 4
대기 중인 트럭의 무게가 4입니다. 현재 큐에는 무게 7 만큼 트럭이 진입한 상태입니다. 다리가 견딜 수 있는 무게는 10 이기 때문에 대기 중인 트럭은 다리에 진입하지 못하는 상황입니다.
대기 중인 트럭이 다리에 진입하기 위해서는 다리 위의 트럭이 빠져나가야 합니다. 남은 거리가 가장 짧은 트럭은 무게 7인 트럭으로 해당 트럭은 다리를 빠져나갑니다. 그리고 그만큼 다른 트럭을 이동시킵니다.
트럭의 이동 거리는 사실상 이동 시간입니다. 따라서 시간을 조정합니다.
이제 다시 대기 중인 무게 4 트럭이 이동할 수 있는지 확인해봅니다. 가능하네요. 따라서 무게 4 트럭은 다리에 진입할 수 있습니다.
3 단계: 대기 중인 트럭의 무게 = 5
조금 빨리 정리해보겠습니다. 대기 중인 트럭의 무게는 5이고 이는 다리에 있는 트럭의 무게 합을 고려했을 때 대기 중인 트럭은 다리에 진입할 수 있습니다. 다리에 진입함에 따라서 이동거리와 시간을 갱신합니다. 이번 예제는 해당사항이 없지만 만약 이 과정에서 다리에 대기 중인 트럭의 남은 이동거리가 0이 되면 해당 트럭을 다리에서 벗어나도록 처리해야 합니다.
4 단계: 대기 중인 트럭의 무게 = 6
대기 중인 트럭의 무게가 6인 경우 트럭이 다리에 바로 진입할 수 있는 상황이 아닙니다. 이후에 살펴보겠지만 다리에 있는 트럭이 모두 다리를 벗어나야 대기 중인 트럭이 다리에 진입할 수 있습니다.
다리에 있는 트럭 중 이동 거리가 가장 짧게 남은 무게 4 트럭을 제거합니다. 그에 따라서 이동 거리와 시간을 갱신합니다.
트럭이 다리를 벗어났음에도 아직 대기 중인 트럭이 다리에 진입하지 못합니다. 현재 다리 위에 있는 트럭이 하나 더 빠져야 합니다.
무게가 5인 트럭을 다리에서 벗어나게 하고, 시간을 갱신합니다.
큐가 비었기 때문에 대기 중인 무게 6 트럭이 다리에 진입할 수 있습니다.
마무리 단계: 다리에 남아있는 트럭 처리
현재 다리에 남아있는 트럭이 완전히 다리를 건너는 시간이 추가되어야 합니다. 이를 위해서는 큐의 마지막 원소의 이동 거리(=이동 시간)를 더해주어야 합니다.
최종적으로 모든 트럭이 다리를 건너는데 소요된 시간은 8입니다.
소스 코드
트럭 이동 함수
# queue 에 있는 트럭을 distance 만큼 이동시킨다. (pop -> 변환 -> push)
# distance 만큼 이동시켰을때 다리를 벗어나는 트럭에 대한 처리 필요 (bridge_weight 감소)
def move_trucks(queue, distance, bridge_weight):
length = len(queue)
for _ in range(length):
w, d = queue.popleft()
# distance 만큼 이동시켰을때 다리를 벗어나지 않는 트럭에 대해서만 push 수행
if d - distance > 0:
queue.append((w, d - distance))
else:
bridge_weight -= w
return bridge_weight
메인 솔루션 함수
from collections import deque
def solution(bridge_length, weight, truck_weights):
queue = deque([]) # 다리 역할은 큐로 구현한다
time = 0 # 경과 시간
bridge_weight = 0 # 다리에 있는 트럭의 무게 합
for truck_weight in truck_weights:
# 현재 트럭이 다리에 진입할 수 있는 경우
if bridge_weight + truck_weight <= weight:
# 트럭 이동과 그에 따른 다리에 있는 트럭 무게 변화 && 시간 경과
bridge_weight = move_trucks(queue, 1, bridge_weight)
time += 1
# 트럭 다리 진입과 그에 따른 다리에 있는 트럭 무게 변화
queue.append((truck_weight, bridge_length))
bridge_weight += truck_weight
# 현재 트럭이 다리에 진입할 수 없는 경우
else:
# 현재 트럭이 다리에 진입할 수 있을때까지 반복
while queue:
# 이동거리가 가장 짧은 트럭 다리 벗어나고 그에 따른 다리에 있는 트럭 무게 변화 && 시간 경과
w, d = queue.popleft()
bridge_weight -= w
bridge_weight = move_trucks(queue, d, bridge_weight)
time += d
if bridge_weight + truck_weight <= weight:
break
# 트럭 다리 진입과 그에 따른 다리에 있는 트럭 무게 변화
queue.append((truck_weight, bridge_length))
bridge_weight += truck_weight
# 다리에 가장 마지막에 위치한 트럭이 다리를 빠져나오는 시간만큼 시간 추가
last_w, last_d = queue.pop()
time += last_d
return time
if __name__ == '__main__':
assert solution(2, 10, [7, 4, 5, 6]) == 8
assert solution(100, 100, [10]) == 101
assert solution(5, 12, [5, 4, 3, 2, 3, 2, 2]) == 14
dhsong95/-PRACTICE-Programmers-Algorithm
Contribute to dhsong95/-PRACTICE-Programmers-Algorithm development by creating an account on GitHub.
github.com
'알고리즘 풀이 > 프로그래머스' 카테고리의 다른 글
| 알고리즘 풀이: [프로그래머스] 쇠막대기 (0) | 2020.05.29 |
|---|---|
| 알고리즘 풀이: [프로그래머스] 프린터 (0) | 2020.05.28 |
| 알고리즘 풀이: [프로그래머스] 기능개발 (0) | 2020.05.27 |
| 알고리즘 풀이: [프로그래머스] 탑 (0) | 2020.05.24 |
| 알고리즘 풀이: [프로그래머스] 가장 큰 수 (0) | 2020.05.23 |
