Stack/Queue: 다리를 지나는 트럭 [Lv2]
문제 설명
트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 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 |
Solution
내 풀이
def solution(bridge_length, weight, truck_weights):
answer = 0
from collections import deque
truck_weights = deque(truck_weights)
bridge = deque(0 for _ in range(bridge_length))
bridge_weight = 0
while truck_weights or any(bridge):
answer += 1
bridge_weight -= bridge.popleft()
if truck_weights and (truck_weights[0] + bridge_weight) <= weight:
bridge.append(truck_weights.popleft())
bridge_weight += bridge[-1]
else:
bridge.append(0)
return answer
Queue를 사용하여 문제 풀이를 했다.
truck_weight에서 앞부터 순서대로 트럭이 지나가기 때문에 popleft()를 사용해야 한다. 그러므로 deque로 바꿔준다.
bridge는 말 그대로 다리를 만든 것이고, append()를 통해 bridge의 맨 뒤에 트럭이 추가되고, 트럭이 다리를 다 지나가면 popleft()를 통해 트럭을 없애준다.
answer은 시간이고, bridge_weight는 현재 다리 위에 있는 트럭들의 무게 합이다.
while문의 조건은 다리를 건너기 위해 대기중인 트럭이 존재하거나, 다리 위에 트럭이 있다면 실행한다는 조건을 적어놓은 것이다.
while문이 한번 실행 될 때마다 시간을 1씩 증가
시간이 1 지남에 따라 bridge에서 0번 index의 값을 없애기 위해 popleft() 하는데, 이 때 트럭이 지나간 것이라면 bridge_weight에서 지나간 트럭의 무게를 빼준다.
그 후에 대기중인 트럭이 존재하고, 그 대기중인 트럭 중 맨 앞차의 무게와 현재의 bridge_weight를 합한 것이 무게 제한보다 작거나 같다면, 해당 대기중인 트럭이 다리에 올라간다.
트럭이 다리에 올라갈 때에 bridge에는 트럭의 무게를 append()한다. 나중에 트럭이 지나갈때, 이 값을 다리 위의 트럭들 무게bridge_weight에서 빼기 때문.
만약 위의 조건이 맞지 않는다면 그냥 다리에 0을 추가하여 트럭이 지나가지 않음을 보여줌.
그냥 코드 순서대로.. 설명하긴 했는데 잘 이해가 될진..
결과
Other's Code
import collections
DUMMY_TRUCK = 0
class Bridge(object):
def __init__(self, length, weight):
self._max_length = length
self._max_weight = weight
self._queue = collections.deque()
self._current_weight = 0
def push(self, truck):
next_weight = self._current_weight + truck
if next_weight <= self._max_weight and len(self._queue) < self._max_length:
self._queue.append(truck)
self._current_weight = next_weight
return True
else:
return False
def pop(self):
item = self._queue.popleft()
self._current_weight -= item
return item
def __len__(self):
return len(self._queue)
def __repr__(self):
return 'Bridge({}/{} : [{}])'.format(self._current_weight, self._max_weight, list(self._queue))
def solution(bridge_length, weight, truck_weights):
bridge = Bridge(bridge_length, weight)
trucks = collections.deque(w for w in truck_weights)
for _ in range(bridge_length):
bridge.push(DUMMY_TRUCK)
count = 0
while trucks:
bridge.pop()
if bridge.push(trucks[0]):
trucks.popleft()
else:
bridge.push(DUMMY_TRUCK)
count += 1
while bridge:
bridge.pop()
count += 1
return count
def main():
print(solution(2, 10, [7, 4, 5, 6]), 8)
print(solution(100, 100, [10]), 101)
print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]), 110)
if __name__ == '__main__':
main()
이 풀이를 하신분은 클래스를 사용해서 풀이를 했다.
클래스를 사용하기에, 여러가지의 테스트케이스를 한번에 테스트 해 볼 수 있는 장점이 있다.
방법 자체는 내 풀이와 비슷하다.
하지만 클래스를 사용해서인지 실제 코드를 실행했을 시에 실행 시간은 조금 차이가 났다.
