[Python] 다리를 지나는 트럭

1. 문제

 

 

 

2. 풀이과정

 

방법 1) 큐에 [트럭 무게, 위치]를 넣고, 반복문 한 번 돌 때마다 위치를 1 감소시켜서 위치 값이 1이 되면 트럭이 다리에서 나간다.

변수 c는 다음에 기다리는 트럭의 truck_weights에서의 인덱스 값을 나타낸다.

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 1
    Q = deque() #다리
    Q.append([truck_weights[0], bridge_length])
    sum = truck_weights[0]

    c = 1
    while Q:
        answer += 1
        if Q[0][1] == 1:#다리 출발(bridge_length)에서 끝(1)까지 도착하면 pop
            out = Q.popleft()
            sum -= out[0]
        
        for i in Q:
            i[1] -= 1

        if c < len(truck_weights) and sum + truck_weights[c] <= weight:
            Q.append([truck_weights[c], bridge_length])
            sum += truck_weights[c]
            c += 1
    
    return answer

 

방법 2) 큐의 길이를 0을 이용해서 일정하게 유지한다.

따라서, 0이든 트럭이든 무조건 하나가 나가고, 다리에 들어갈 때도 마찬가지로 0이든 트럭이든 무게만 맞게 하나 들어오도록 한다.

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    Q = deque(0 for _ in range(bridge_length))
    c = 0 #다리에 들어간 트럭 수
    sum = 0
    
    while c < len(truck_weights):
        answer += 1
        a = Q.popleft()
        sum -= a
        
        if sum + truck_weights[c] <= weight:
            Q.append(truck_weights[c])
            sum += truck_weights[c]
            c += 1
        else:
            Q.append(0)
            
    answer += bridge_length 
    #마지막 트럭이 다리에 도착하면 반복문이 끝남
    #마지막 트럭이 끝까지 도착할 때까지의 시간 더해주기
    
    return answer

 

방법 3) Bridge 클래스를 만들어서 나타내었다. 알고리즘은 방법 2)와 동일하다

from collections import deque

class Bridge(object):
	#초기화
    def __init__(self, length, weight):
        self.max_weight = weight
        self.queue = deque(0 for _ in range(length))
        self.weight = 0
        
    #bridge에 들어올 때
    def enqueue(self, truck):
        if self.weight + truck[0] <= self.max_weight:
            a = truck.popleft()
            self.weight += a
            self.queue.append(a)
        else:
            self.queue.append(0)
            
    #bridge에서 나가기  
    def dequeue(self):
        self.weight -= self.queue.popleft()

def solution(bridge_length, weight, truck_weights): #메인함수
    answer = 0
    truck = deque(w for w in truck_weights)
    bridge = Bridge(bridge_length, weight)
    
    while truck:
        answer += 1
        #데이터가 있는 칸이든 없는 칸(0)이든 하나 나가고 하나 들어옴
        bridge.dequeue()
        bridge.enqueue(truck) #0 또는 트럭하나 들어옴
        
    answer += bridge_length
     
    return answer