[프로그래머스/42583/level2/고득점kit] 다리를 지나는 트럭 - 큐, sum 사용 시간초과 해결

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42583

• deque 사용하기

deque의 popleft() 삭제시간은 O(1) / list의 pop(0) 은 O(n)이다.

 

첫 풀이 - 시간초과 실패

• HOW?
  • 트럭이 선입선출로 나가니까 큐를 사용함
  • 어려웠던 부분 : 최대 트럭 개수 유지법 = 1개 pop하고 무조건 1개 append하는 로직이기때문에 가능
  • 대기 트럭이 없으면 그때부터는 다리를 건너는 트럭이 없어질때까지 POP하다가 종료됨
• 시간초과 이유
  • sum이 O(n)이다보니 도로 최대길이가 길때 시간초과가 나는 듯 → 변수에 누적으로 수정함

'''
- 트럭이 선입선출로 나가니까 큐를 사용함
- 최대 트럭 개수 유지법 = 1개 pop하고 무조건 1개 append하는 로직이기때문에 가능
'''
from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0

    #다리를 건너는 트럭
    queue = deque([0] * bridge_length) #최대 트럭개수만큼 빈칸 만들어둠

    while queue:
        queue.popleft()
        answer += 1

        if truck_weights:
            if sum(queue) + truck_weights[0] <= weight:
                #새로 트럭이 들어와도 되는 경우
                queue.append(truck_weights.pop(0))
            else:
                #새로 트럭이 들어올 수 없는 경우 빈자리만 추가
                queue.append(0)
        
    return answer

시간초과 해결 코드

'''
- 트럭이 선입선출로 나가니까 큐를 사용함
- 최대 트럭 개수 유지법 = 1개 pop하고 무조건 1개 append하는 로직이기때문에 가능
'''
from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0

    #다리를 건너는 트럭
    queue = deque([0] * bridge_length) #최대 트럭개수만큼 빈칸 만들어둠
    
    **#무게 누적
    cur_weight = 0**

    while queue:
        cur_weight -= queue.popleft()
        answer += 1

        if truck_weights:
            **if cur_weight + truck_weights[0] <= weight:
                #새로 트럭이 들어와도 되는 경우
                cur_truck = truck_weights.pop(0)
                queue.append(cur_truck)
                cur_weight += cur_truck**
            else:
                #새로 트럭이 들어올 수 없는 경우 빈자리만 추가
                queue.append(0)
        
    return answer