[プログラマー]ブリッジトラック(Lv 2,Python 3)

質問する

2つの仮定がありません🤬

に答える

アイデア

solution.py

from collections import deque

def solution(bridge_length, weight, truck_weights):
    
    truck_weights = deque(truck_weights)  # 넣고 빼고 할 때 시간복잡도 낮추기 위해 deque로 선언
    
    cur_truck_weight_lst = deque()  # 지금 다리 위에 있는 트럭들의 무게
    cur_truck_loc_lst = deque()  # 지금 다리 위에 있는 트럭들의 위치
    time = 0

    while True:
        time += 1

        # 다리 위에 있는 트럭들 한 칸씩 앞으로 이동
        for idx, val in enumerate(cur_truck_loc_lst):
            cur_truck_loc_lst[idx] = val+1

        # 가장 앞에 있는 트럭이 끝까지 건넜는지 확인해서, 건넜으면 cur에서 제거
            # 트럭은 한 대 씩만 올라오고, 속도는 1로 같기 때문에 여러 대가 동시에 도착하는 경우는 없음
        if cur_truck_loc_lst and (cur_truck_loc_lst[0] == bridge_length):
            cur_truck_weight_lst.popleft()
            cur_truck_loc_lst.popleft()

        # 도착한 트럭을 제외한 나머지 트럭 무게의 총합
        cur_weight_sum = sum(cur_truck_weight_lst)

        # 대기중인 트럭이 있고, 현재 무게가 허용무게보다 가벼울 경우
        if truck_weights and (cur_weight_sum < weight):
            next_truck_weight = truck_weights.popleft()
            
            # 다음 순서 트럭이 올라가도 허용무게 이하라면, 올림
            if cur_weight_sum + next_truck_weight <= weight:
                cur_truck_weight_lst.append(next_truck_weight)
                cur_truck_loc_lst.append(0) 
            
            # 아니면 다시 대기
            else : truck_weights.appendleft(next_truck_weight)
    
        # 대기중이거나 다리 위에 트럭이 하나도 없을 경우 종료
        if not truck_weights and not cur_truck_loc_lst:
            break
            
    return time

実行結果

より良い回答

アイデア

solution.py

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque(0 for _ in range(bridge_length))
    total_weight = 0
    step = 0
    truck_weights.reverse()

    while truck_weights:
        total_weight -= bridge.popleft()
        if total_weight + truck_weights[-1] > weight:
            bridge.append(0)
        else:
            truck = truck_weights.pop()
            bridge.append(truck)
            total_weight += truck
        step += 1

    step += bridge_length

    return step