다리를 지나는 트럭

• 문제 설명
  
  • 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
    
    
  • 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
    

    

    
    
    
    
  • 따라서, 모든 트럭이 다리를 지나려면 최소 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 이하입니다.
• 입출력 예

 

 

• 문제 풀이 1
  • 문제를 보고 일단 테스트 코드에 나와 았는 부분으로 손로직 구상
  • [0 0 7 0 4 5 0 6], [0*100 10], [0*100 10 10 10 10 10 10 10 10 10 10]의 규칙이 이 보였다
  • 이를 통하여 코드 작성
  • 그런데 코드를 작성한 걸로 테스트 코드는 통과가 되나 테스트 1,4,5,6,8,9,10이 실패
  • 문제를 보니 직전 수만 비교하는 것을 확인

def solution(bridge_length, weight, truck_weights):
    answer = bridge_length
    temp = 0
    for truck in truck_weights:
        if temp == 0 or temp + truck <= weight:
            answer += 1
        else:
            answer += bridge_length
        temp = truck
        
    return answer

 

• 문제 풀이 2
  • 위의 의 문제로 바로 더하기 값을 추가하는 방식으로 진행
  • 큐를 이용하여 초기에 전체 대기 시간을 주고 그것을 초단위로 계산하는 방식으로 구현
  • 다 통과 되었으나 테스트 5번에서 시간 초과로 실패

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    queue = deque([0] * bridge_length)
    truck_weights = truck_weights[::-1]
    
    while queue:
        queue.popleft()
        if truck_weights and sum(queue) + truck_weights[-1] <= weight:
            queue.append(truck_weights[-1])
            truck_weights.pop()
        elif truck_weights:
            queue.append(0)
            
        answer += 1
    return answer

 

 

• 문제 풀이 3
  • 위 코드에서 sum(queue) 부분에서 시간복잡도가 올라가서 그부분을 따로 컨트롤 할 수 있도록 구현

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    queue = deque([0] * bridge_length)
    truck_weights = truck_weights[::-1]
    total = 0
    while queue:
        check = queue.popleft()
        if check > 0 :
            total -= check
            
        if truck_weights and total + truck_weights[-1] <= weight:
            queue.append(truck_weights[-1])
            total += truck_weights[-1]
            truck_weights.pop()
            
        elif truck_weights:
            queue.append(0)
            
        answer += 1
    return answer