[PYTHON] 프로그래머스 #42583 다리를 지나는 트럭

문제

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

 

 

 

나의 풀이

 

트럭의 길이에 꽂혀서 초반에 문제를 이해하는데 오래걸렸다. 트럭의 길이는 1이었음

bridge_length 길이의 배열을 만들어서 0으로 채워주고, 큐를 사용해서 insert와 pop으로 풀었다.

맨날 append랑 기본 pop만 사용하다가 살짝 당황했다

 

arr.insert(n, x) -> arr[n]에 x넣기 (나머지는 뒤로 밀림)

arr.pop(0), arr.popleft() -> 맨 앞 pop하기

def solution(bridge_length, weight, truck_weights):

    count = 0
    arr = bridge_length * [0]

    while True:
        #  맨 뒤 나가기
        arr.pop()
        if (truck_weights[0] + sum(arr)) <= weight:
            #  맨 앞에 추가
            arr.insert(0, truck_weights.pop(0))
        else:
            arr.insert(0, 0)
        count += 1
        if len(truck_weights) == 0:
            break

    return count + bridge_length

 

근데 테스트 5에서 시간초과가 났다

 

 

sum()은 O(N)이라 이 부분에서 시간이 오래 걸린다는 조언을 보고 current로 바꿔줬다

def solution(bridge_length, weight, truck_weights):
    # count : 소요 시간 
    # arr : 다리의 길이만큼 배열 생성
    # current : 현재 다리 위의 무게의 합
    
    count = 0 
    arr = bridge_length * [0]
    current = 0 

    while True:
        #  맨 뒤 트럭 나가기
        current -= arr.pop() 
        
        if (truck_weights[0] + current) <= weight:
        #  맨 앞에 새 트럭 추가
            arr.insert(0, truck_weights.pop(0)) 
            current += arr[0]
        else:
            arr.insert(0, 0)
            
        count += 1
        
        #  대기 트럭이 더이상 없으면 break
        if len(truck_weights) == 0:
            break

	#  지금까지 소요시간 + 마지막 트럭이 다리를 끝까지 건너는데 걸리는 시간 리턴
    return count + bridge_length 

sum이 포문을 돌면서 다 더하는거라더니 진짜 시간이 오래걸리나보다

이렇게 바꿔주니까 채점도 훨씬 빨리 끝남!!