Solution :
1. Stack 풀이 :
## 스택
def solution(bridge_length, weight, truck_weights):
# 초기화
time = 0
bridge=[0]*bridge_length # 다리
weight_sum=0
# 트럭이 빌 때까지 반복문 돌림.
while truck_weights:
weight_sum=weight_sum-bridge.pop(0)
time+=1
if weight_sum + truck_weights[0] <= weight : # weight 이하라면
first_truck=truck_weights.pop(0) # 첫번째 트럭
bridge.append(first_truck) # 다리위에 추가.
weight_sum+=first_truck
# print('1 :',bridge, time)
else:
bridge.append(0) # 다리위에 추가.
# print('2 :',bridge, time)
return time+len(bridge) # 마지막에 올라온 트럭은 while 문에 진입하지 못함으로, 길이만큼 초가 필요함.
2. queue 풀이 :
## 큐
from collections import deque
def solution(bridge_length, weight, truck_weights):
# 초기화
time = 0
bridge=[0]*bridge_length # 다리
q_bridge=deque(bridge) # q_다리
q_truck_weights=deque(truck_weights) # q_트럭무게
current_weight = 0
# 트럭이 빌 때까지 반복문 돌림.
while q_truck_weights:
first_truck=q_truck_weights[0]
current_weight = current_weight-q_bridge.popleft() # 다리에서 맨 앞칸을 제외한 무게.
# 새롭게 트럭을 추가 유무
if current_weight + first_truck <= weight : # 기존무게 + 새로운 트럭무게 <= weight 라면
first_truck = q_truck_weights.popleft() # 첫번째 트럭을 추가함
q_bridge.append(first_truck) # 다리위에 추가.
current_weight+=first_truck
time+=1
# print('1 :',q_bridge, time)
else:
q_bridge.append(0) # 다리위에 추가.
time+=1
# print('2 :',q_bridge, time)
return time+len(q_bridge)
Skills :
- current_weight 가 필요함 :
- 만약 아래와 같이 sum 함수를 사용한다면, 시간초과가 발생. ( 최악의 경우에 while문도 10⁴ 이고 sum도 10⁴ 임으로 -> 10⁸ 이 됨으로 시간초과.
while q_truck_weights:
first_truck=q_truck_weights[0]
weight_bridge =sum(q_bridge) # while 이랑, sum 하면 10000*10000 = 10^8 이라 에러남. (10^7 까지 안전.)
weight_bridge = weight_bridge-q_bridge.popleft() # 다리의 첫번째 부분이 나갔음.
# 새롭게 트럭을 추가 유무
if first_truck + weight_bridge <= weight : # weight 이하라면
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] LV1 데이터분석 | 파이썬 (0) | 2025.05.07 |
---|---|
[프로그래머스] LV2 주식가격 | 파이썬 (0) | 2025.05.07 |
[프로그래머스] LV2 기능개발 | 파이썬 (0) | 2025.05.07 |
[프로그래머스] LV2 프로세스 | 파이썬 (0) | 2025.05.07 |
[프로그래머스] LV2 의상 | 파이썬 (0) | 2025.05.07 |