📝 다리를 지나는 트럭 (Level 2)
스택/큐
다리를 지나는 트럭
🔹Python
- 다른 사람의 풀이
def solution(bridge_length, weight, truck_weights):
time = 0
bridge = [0] * bridge_length
currentWeight = 0
while len(truck_weights) > 0:
time += 1
# print(f"time: {time}, bridge: {bridge}")
# 다리에서 나가는 트럭 처리
currentWeight -= bridge.pop(0)
# 다리에 들어올 수 있는 트럭 처리
if currentWeight + truck_weights[0] <= weight :
currentWeight += truck_weights[0]
bridge.append(truck_weights.pop(0))
else:
bridge.append(0)
# 마지막 트럭이 다리를 지나는 시간 추가
time += bridge_length
return time
- deque 사용 풀이
from collections import deque
def solution(bridge_length, weight, truck_weights):
time = 0
bridge = deque([0] * bridge_length) # list -> deque
truck_weights = deque(truck_weights) # list -> deque
currentWeight = 0
while len(truck_weights) > 0:
time += 1
# print(f"time: {time}, bridge: {bridge}")
# 다리에서 나가는 트럭 처리
currentWeight -= bridge.popleft()
# 다리에 들어올 수 있는 트럭 처리
if currentWeight + truck_weights[0] <= weight :
currentWeight += truck_weights[0]
bridge.append(truck_weights.popleft())
else:
bridge.append(0)
# 마지막 트럭이 다리를 지나는 시간 추가
time += bridge_length
return time📚 배울 점
deque : collections 모듈의 deque는 double-ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조
deque는 list에는 없는 popleft()라는 메서드를 제공한다. 이 메서드를 사용하면 첫 번째 데이터를 제거할 수 있다. 데이터의 흐름은 list 객체의 pop(0) 메서드를 사용할 때 처럼 뒤에서 앞으로 흐른다.
deque는 appendleft(x)의 메서드는 데이터를 맨 앞에서 삽입할 수 있다. 이는 list 객체의 insert(0, x) 메서드와 유사하다.
>>> from collections import deque
>>>
>>> queue = deque([4, 5, 6])
>>> queue.append(7)
>>> queue.append(8)
>>> queue
deque([4, 5, 6, 7, 8])
>>> queue.popleft()
4
>>> queue.popleft()
5
>>> queue
deque([6, 7, 8])
>>> queue.appendleft(3)
>>> queue.appendleft(2)
>>> queue
deque([2, 3, 6, 7, 8])list.pop(0)의 시간복잡도는 O(N)이고 dequeue.popleft()의 시간복잡도는 O(1)이므로 시간복잡도 측면에서 deque를 사용하는 것이 유리하다.
하지만 deque는 무작위 접근(random access)의 시간 복잡도가 O(n)이라는 단점이있다. 내부적으로 linked list를 사용하고 있기 때문에 i번째 데이터에 접근하려면 맨 앞/뒤부터 i번 순회가 필요한다.
🔸Java
- 다른 사람의 풀이
import java.util.*;
class Solution {
class Truck {
int weight;
int move;
public Truck(int weight) {
this.weight = weight;
this.move = 1;
}
public void moving() {
move++;
}
}
public int solution(int bridgeLength, int weight, int[] truckWeights) {
Queue<Truck> waitQ = new LinkedList<>();
Queue<Truck> moveQ = new LinkedList<>();
for (int t : truckWeights) {
waitQ.offer(new Truck(t));
}
int answer = 0;
int curWeight = 0;
while (!waitQ.isEmpty() || !moveQ.isEmpty()) {
answer++;
if (moveQ.isEmpty()) {
Truck t = waitQ.poll();
curWeight += t.weight;
moveQ.offer(t);
continue;
}
for (Truck t : moveQ) {
t.moving();
}
if (moveQ.peek().move > bridgeLength) {
Truck t = moveQ.poll();
curWeight -= t.weight;
}
if (!waitQ.isEmpty() && curWeight + waitQ.peek().weight <= weight) {
Truck t = waitQ.poll();
curWeight += t.weight;
moveQ.offer(t);
}
}
return answer;
}
}📚 배울 점
0. 초기 상태 (time = 0)
waitQ = [(7, 1), (4, 1), (5, 1), (6, 1)]
moveQ = []
curWeight = 0
1. 1초 (time = 1)
7 트럭을 다리에 올림
waitQ = [(4, 1), (5, 1), (6, 1)]
moveQ = [(7, 1)]
curWeight = 7
2. 2초 (time = 2)
moveQ의 모든 트럭을 한 칸 앞으로 이동: [(7, 2)]
4 트럭을 다리에 올릴 수 없음 (curWeight + 4 = 11 > 10)
waitQ = [(4, 1), (5, 1), (6, 1)]
moveQ = [(7, 2)]
curWeight = 7
3. 3초 (time = 3)
moveQ의 모든 트럭을 한 칸 앞으로 이동: [(7, 3)]
7 트럭이 다리를 건너므로 moveQ에서 제거
curWeight = 0
4 트럭을 다리에 올림
waitQ = [(5, 1), (6, 1)]
moveQ = [(4, 1)]
curWeight = 4
time = 3
4. 4초 (time = 4)
moveQ의 모든 트럭을 한 칸 앞으로 이동: [(4, 2)]
5 트럭을 다리에 올림 (curWeight + 5 = 9 <= 10)
waitQ = [(6, 1)]
moveQ = [(4, 2), (5, 1)]
curWeight = 9
5. 5초 (time = 5)
moveQ의 모든 트럭을 한 칸 앞으로 이동: [(4, 3), (5, 2)]
4 트럭이 다리를 건너므로 moveQ에서 제거
curWeight = 5
6 트럭을 다리에 올릴 수 없음 (curWeight + 6 = 11 > 10)
waitQ = [(6, 1)]
moveQ = [(5, 2)]
curWeight = 5
6. 6초 (time = 6)
moveQ의 모든 트럭을 한 칸 앞으로 이동: [(5, 3)]
5 트럭이 다리를 건너므로 moveQ에서 제거
curWeight = 0
6 트럭을 다리에 올림
waitQ = []
moveQ = [(6, 1)]
curWeight = 6
7. 7초 (time = 7)
moveQ의 모든 트럭을 한 칸 앞으로 이동: [(6, 2)]
6 트럭이 아직 다리를 건너지 않음
curWeight = 6
8. 8초 (time = 8)
moveQ의 모든 트럭을 한 칸 앞으로 이동: [(6, 3)]
6 트럭이 다리를 건너므로 moveQ에서 제거
curWeight = 0
로직이 이해가 안가서 gpt한테 물어봤다 ...
