[프로그래머스] 다리를 지나는 트럭 (Lv2, Python3)
9090 단어 다리를 지나는 트럭프로그래머스Python3Python3
문제
두 가지 가정이 빠져있음 🤬
- 트럭의 속도는 1 per sec
- (무게에 여유가 있더라도) 한 턴에 대기열 맨 앞 트럭 한 대만 올라갈 수 있다.
풀이
아이디어
- 무한루프 돌리면서
time += 1
- 매 loop 마다
- 이동중인 트럭 한 칸씩 앞으로 전진
- 무게 여유 있을 때 대기중인 트럭 출발 (한 loop에 한 대씩 만)
- 대기중인 트럭 없고, 이동중인 트럭도 없으면 loop 종료
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
수행결과
더 좋은 풀이
아이디어
-
다리 길이 만큼의
deque
를 만들고, 다리 위의 각 자리에 트럭을 배치, 1초마다 re-indexing하여 한 칸씩 앞으로 옮김다리를
deque
로, index로 현재 건너고 있는 트럭의 위치를 표현하는 방식 🤭
index : 0
이면 다리의 가장 끝 (다음 loop에 다리 다 건넘) -
truck_weights
앞에서부터 하나씩 빼올 때 시간복잡도 낮추기 위해reverse
시킨 후에pop()
해서 하나씩 뺌
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
Author And Source
이 문제에 관하여([프로그래머스] 다리를 지나는 트럭 (Lv2, Python3)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@khhwangv/프로그래머스Lv2다리를-지나는-트럭Python3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)