[221116]プログラマ-ブリッジトラック

マッチングだけで、もっと良い答えではありません.
[プログラマー-橋を渡るトラック]

と知る

1-1. スタック

後ほど入力するデータ先出後出(LIFO)のデータ構造

輸出入が同じ

1-2. スタック実装

2-1. キュー

先進データ先進先出資料構造

入口も出口も貫通したトンネルのようです.

2-2. キュー実装

2-3. list vs Queue vs deque
ListQueuedequeターゲット汎用性大列資料構造マルチスレッド環境でリソースを安全に交換する一方向キュー両端キューはキューよりも速い双方向キューを実現24791422479142利点n個の要素が直ちに挿入/削除にアクセスできる後、shitfなしで双方向から削除/挿入できる.使用可能なスタックエンドポイントの削除/挿入を完了し、関連要素を1つずつ移動する柔軟な演算リンクlistnは2番目の要素にアクセスしにくい
2-4. 比較時間の複雑さ

import time
import sys, collections

L = []
for i in range(1, 60000000):
    L.append(i)
dq = collections.deque(L)

start_time1 = time.time()
d1 = L[30000000]  # list 접근
print(time.time() - start_time1)  # 0.0

start_time2 = time.time()
d2 = dq[30000000]  # deque 접근
print(time.time() - start_time2)  # 0.037924766540527344

start_time3 = time.time()
L.insert(0,10)  # list 삽입
print(time.time() - start_time3)  # 0.060869693756103516

start_time4 = time.time()
dq.appendleft(10)   # deque 삽입
print(time.time() - start_time4)  # 0.0

質問する

何台ものトラックが車道橋を通る
橋の長さ、橋が耐えられる重量、トラックが並ぶとき
すべてのトラックが橋を渡るのに必要な最短時間を見つけてください.
条件

ブリッジ最大上り可能ブリッジlentgh台

Weigth以下の重量に耐える

橋を完全に登っていないトラックは

を無視している.
ex
最大2台までアップグレード可能
10ポンドの重量に耐えられる
重量は[7,4,5,6]の順に橋を通過します
タイムブリッジ通過待ちトラック0[-]7、4、5、61[-7]4、5、62[7-]4、5637[-4]5647[4.5]657、4[5-]667、4、5[-6]77、4、5[6-]87、4、5[6-]87、4、5[6-]87、4、5[6-]87、4、5、5、6[-]

私の答え

def solution(bridge_length, weight, truck_weights):
   sec = 0	# 경과시간
   bridge = [0] * bridge_length	# 다리 위 트럭 배열
   while bridge:		# 다리 위에 트럭이 모두 지나갈 동안
       bridge.pop(0)		# 가장 앞의 트럭 탈출
       if truck_weights:	# 대기하는 트럭이 존재한다면
	   # 다리 위 트럭의 무게 + 앞으로 진입할 트럭의 무게 <= 다리가 견딜 수 있는 무게
           if sum(bridge) + truck_weights[0] <= weight:
               bridge.append(truck_weights.pop(0)) # 대기하는 트럭 순서대로 삽입
           else: 		# 다리가 견딜 수 없다면
               bridge.append(0) # 다리 길이 유지를 위해 삽입
        sec += 1 		# 시간 증가
   return sec

より良いソリューション

from collections import deque

def solution(bridge_length, weight, truck_weights):
   sec = 0
   bridge = deque([0] * bridge_length)
   truck = deque(truck_weights)	# 트럭 배열도 deque
   current_weights = 0		# 현재 다리 위 무게
   while bridge:
       current_weights -= bridge.popleft() # 탈출하는 트럭은 무게에서 제외
       if truck:
           if current_weights + truck[0] <= weight:
               in_truck = truck.popleft()
               bridge.append(in_truck)
               current_weights += in_truck # 진입하는 트럭은 무게에 추가
           else:
               bridge.append(0)
       sec += 1
   return sec