백준 - 트럭(13335)

 

13335번: 트럭

접근 방법

• 큐로 풀면 될 것 같다. 크게 2가지가 있다.
  • 트럭이 나와야할 시간 체크하기
    1. 트럭을 큐에 넣을 때 진입하는 시간을 같이 넣는다.
    2. 트럭이 나올 때가 됐는지 시간별로 체크한다.(트럭시간 + L이 나올 시간이다.)
  • 트럭이 이동하는 다리 시뮬레이트 하기
    1. 시간마다 실제로 트럭의 무게를 큐에 넣는다.
    2. 트럭이 들어가지 않아야할 때는 0을 넣는다.
    3. 시간마다 큐에서 pop한다.

트럭이 나와야 할 시간 체크하기

from collections import deque
N,L,W = map(int,input().split())
A = deque([*map(int,input().split())])

t=0
Q=deque([])
totalWeight = 0
while A:
  t+=1
  if(Q and t>=Q[0][1]+L):
    pop_truck = Q.popleft()
    totalWeight -= pop_truck[0]
  next_truck = A[0]
  if(totalWeight+next_truck<=W):
    next_truck = A.popleft()
    Q.append((next_truck,t))
    totalWeight += next_truck
print(t+L)

• 마지막 코드를 보면 할 수 있듯이 시간을 실제로 1씩 계속 더할 필요는 없다. 뒷트럭이 못 들어가고, 맨 앞의 트럭이 나오기 전까지는 의미없이 시간을 더하고, 비교하는 로직이 반복될 것이다.
• 따라서 아래와 같이 시간계산을 최적화할 수 있다.

from collections import deque
N,L,W = map(int,input().split())
A = [*map(int,input().split())]

t=0
Q=deque([(0,0)])
totalWeight = 0
isfull=False
Ai=0
while Ai<N:
  if(not isfull):
    t+=1
  else:
    t=Q[0][1]+L

  if(t>=Q[0][1]+L):
    pop_truck = Q.popleft()
    totalWeight -= pop_truck[0]
    isfull = False

  if(totalWeight+A[Ai]<=W):
    next_truck = A[Ai]
    Ai+=1
    Q.append((next_truck,t))
    totalWeight += next_truck
  else:
    isfull = True

print(t+L)

• A도 실제로 큐로 변환한 뒤 pop 할 필요는 없기 때문에, 조금이라도 overhead를 줄여보고자 index로 훑도록 하였다.

트럭 이동 시뮬레이트 하기

• pypy 기존 풀이 중에서 가장 빠른 코드를 좀더 최적화했다.

from collections import deque
n, w, l = map(int, input().split())
mylist = list(map(int, input().split()))

bridge = deque([0]*w)
count = 0
arrivecnt = 0
weight = 0

while bridge:
  arrive = bridge.popleft()
  weight -= arrive

  if len(mylist) != 0:
    if weight + mylist[0] <= l:
      weight += mylist[0]
      bridge.append(mylist.pop(0))
    else:
      bridge.append(0)
  count += 1

print(count)

예상 속도

• 시간 최적화한 트럭 시간 계산 > 트럭 시간 계산 > 큐로 구현한 시뮬레이트 > 배열로 구현한 시뮬레이트

결과

• 실제 백준 제출 결과는 좀 이상하다.

아래 살짝 숨어있는 4달 전 틀렸습니다가 보이시나요?

• 위부터 순서대로
  • 배열 구현 시뮬레이트
  • 큐 구현 시뮬레이트
  • 시간 최적화 트럭 시간 계산 ( A 배열 index로 접근)
  • 시간 최적화 트럭 시간 계산 ( A 큐 pop)
  • 트럭시간 계산
• 아마도 다리 길이가 1000이하로 너무 작아서 다른 오버헤드가 훨씬 많이 차지하는 것 같다.

정글에서는 시뮬레이트를 어떻게 할지 고민했던 문제였는데 이번에 다시 풀어보니 빠른시간 안에 풀렸다. 성장했음을 느낄 수 있는 문제였다!