프로그래머스 다리를 지나는 트럭

다리의 길이만큼 q를 0으로 채운다.

시간은 0초부터 시작

다리가 있는 동안 반복

매 루프마다 1초씩 더한다

q의 맨 앞 값을 pop하는 이유는 트럭이 지나감을 표현하기 위해서다

트럭 배열이 있다면

    다리에 있는 트럭 무게+대기 중인 트럭 무게<=한계 무게인 경우, 대기 중인 트럭을 다리에 싣는다.

    다리의 하중 초과면 q에 0을 넣어서 트럭을 왼쪽으로 이동시킨다.

def solution(bridge_length, weight, truck_weights):
    q=[0]*bridge_length
    sec=0
    while q:
        sec+=1#시작했으므로 1초씩 더함
        q.pop(0)#트럭이 지나감
        if truck_weights:
            if sum(q)+truck_weights[0]<=weight:#다리에 있는 트럭의 무게와 대기 중인 트럭의 무게가 제한 무게보다 작거나 같다면
                q.append(truck_weights.pop(0))#다리에 트럭 올림
            else:
                q.append(0)#중량 초과면 트럭 안올림
    return sec
print(solution(2,10,[7,4,5,6]))
print(solution(100,100,[10]))
print(solution(100,100,[10,10,10,10,10,10,10,10,10,10]))

위 코드는 시간 초과가 뜬다.

아마도 deque보다 성능이 안좋은 list를 queue처럼 썼기 때문이고, pop(0)을 하면서 n만큼의 시간 복잡도가 계속 생긴다. 그리고 sum()을 해서 다리의 길이만큼의 시간 복잡도가 발생한다.

반복을 줄이기 위해 다리에 오른 트럭이 다리를 완전히 통과할 경우 트럭 자체를 pop했다. 트럭을 pop하면서 다음에 다리에 올릴 트럭의 포인터를 따라가줘야 한다.

다시 푼 풀이

from collections import deque


def solution(bridge_length, weight, truck_weights):
    sec = 1  # 처음부터 트럭을 다리에 올린다.
    s = truck_weights[0]  # 다리에 올라간 트럭의 총 무게
    truck_weights = deque(truck_weights)  # deque 자료구조화
    trucks_on_bridge = deque([[truck_weights[0], 1]])  # 다리에 올라간 트럭을 구분. (트럭 무게, 해당 트럭이 다리 위에 있는 시간)
    truck_idx = 1  # 다음에 다리에 오를 트럭을 가리킴
    while truck_weights:  # 올릴 트럭이 남아 있는 동안 반복
        sec += 1  # 1초 증가
        if truck_idx < len(truck_weights):  # 트럭을 이미 다 올려 트럭이 없으면 다리에 트럭 안올림
            if s + truck_weights[truck_idx] <= weight:  # 지금 올려야하는 트럭과 다리 위 트럭 무게 총합이 weight 이하면
                s += truck_weights[truck_idx]  # 트럭 올리기
                trucks_on_bridge.append([truck_weights[truck_idx], 0])  # 무게, 초
                truck_idx += 1  # 다음 트럭 가리킴
        for truck in trucks_on_bridge:  # 다리 위에 있는 모든 트럭에 대해
            truck[1] += 1  # 각 트럭이 다리 위에서 이동한 시간 1초 증가. 즉, 1칸 이동
        if trucks_on_bridge and trucks_on_bridge[0][1] == bridge_length:  # 맨 끝에 있는 트럭이 다리를 다 지났다면
            s -= trucks_on_bridge[0][0]  # 다리를 통과한 트럭 무게는 다리에 있는 트럭 무게 총합에서 빼기
            trucks_on_bridge.popleft()  # 다리 위 트럭 빼기
            truck_weights.popleft()  # 트럭 빼기
            truck_idx -= 1  # 트럭이 빠졌으므로 인덱스를 -1만큼 옮겨 다음에 올릴 트럭 포인터 유지하기
    sec += 1
    return sec

https://programmers.co.kr/learn/courses/30/lessons/42583?language=python3