다리를 지나는 트럭 (코딩테스트, 프로그래머스)

문제

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

코딩테스트 연습 - 다리를 지나는 트럭

 

아이디어

문제를 보고 이해한 결과 슬라이딩 윈도우 개념을 넣으면 되겠다고 생각했다.

window를 사용하여 다리에 있는 트럭을 비유하고 window에 있는 값의 합이 weight를 넘어가지 않게 한다.

window에 옮기기 전에 합산이 weights를 넘어간다면 -> 트럭대신 0을 추가한다.

truck 리스트가 비면 다 넘어갔다고 생각하고 window에 트럭이 남았기 때문에 answer+window의 길이를 더하면 된다.

 

 

첫번째 시도

from collections import deque
def solution(bridge_length, weight, truck_weights):
    truck=deque(truck_weights)
    window=deque([0 for i in range(bridge_length)])
    answer=deque([])
    
    while truck:
        if (sum(window)-window[0]+truck[0])<=weight:
            answer.append(window.popleft())
            window.append(truck.popleft())
        else:
            answer.append(window.popleft())
            window.append(0)

    
    return len(answer)+len(window)

첫번째 시도 결과

다른 코드도 작성해서 시도해보았으나 테스트 5를 통과하지 못하여 다른 사람 코드를 보고 내 코드를 수정함

수정 코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    window=[0 for i in range(bridge_length)]
    answer=0
    
    while truck_weights:
        if (sum(window)-window.pop(0)+truck_weights[0])<=weight:
            window.append(truck_weights.pop(0))
        else:
            window.append(0)
        answer+=1

    return answer+len(window)

deque를 쓰니 속도가 느려졌다.(?)

일반 리스트를 쓰니 어찌됬든 통과되었다.

시도 결과