문제
https://programmers.co.kr/learn/courses/30/lessons/42583
아이디어
1초를 단위시간으로 잡고 1초씩 지나면서 다리 위 트럭을 이동시키는 방법이 있지만, 허용 무게가 작고 다리가 길면 쓸 데 없는 연산이 많을 것이라는 생각에 바로바로 다음 행동으로 넘어가는 방법을 생각하였다. 다리가 가득 차면 트럭이 나갈 때 까지 기다리지 않고 바로 시간을 이동하는 방법이다.
다리를 deque로 선언한 뒤, 현재 다리 위 트럭의 무게 합 now_w와 총 시간 total_t를 선언한다.
무게가 가득찰 때까지 트럭을 다리에 순서대로 넣는다. 넣을 때마다 총 시간을 1 증가시킨다. (1초 뒤 다리를 한칸씩 지나므로)
다리에 트럭을 [넣은시간, 무게] 자료 형식으로 넣은 뒤
더 이상 넣을 트럭이 없을 때, 다리의 제일 앞 트럭을 빼내면서 now_w에 트럭 무게를 빼고, 시간을 트럭이 들어간 시간 + 다리 길이로 바꾸어 트럭이 나왔을 시간으로 바꾼다.
-> 모든 트럭을 다리에 넣을 때 까지 반복 한 뒤
마지막으로 들어간 트럭의 시간 + 다리 길이를 하면 총 시간이 구해진다.
주의사항 : 예제 3번처럼 다리가 가득 차는 형태라면 시간이 역행되는 연산이 나올 수도 있다. 이미 total_t가 트럭이 나간 시간보다 뒤일 수 도 있다. 트럭을 다리에서 뺄 때 total_t = max( 트럭이 들어간 시간 + 다리길이, total_t)로 한다.
구현
from collections import deque
def solution(bridge_length, weight, truck_weights):
Q = deque()
total_t = 1
now_w = 0
cur = 0
while cur < len(truck_weights):
while cur < len(truck_weights) and (now_w + truck_weights[cur]) <= weight and len(Q) < bridge_length:
Q.append([total_t,truck_weights[cur]])
now_w += truck_weights[cur]
cur += 1
total_t += 1
outs = Q.popleft()
now_w -= outs[1]
total_t = max(outs[0] + bridge_length,total_t)
if Q:
total_t = Q[-1][0] + bridge_length
return total_t결과
느낀 점
생각보다 반례가 많아서 틀린 제출이 많았다. programmers는 테스트 케이스 추가하기가 귀찮아서, 테스트를 대충하는 경향이 있는데 메인 함수로 실행할 때 테스트 케이스를 넣는 습관을 들여야겠다.
