프로그래머스 - 다리를 지나는 트럭 (스택,큐)

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

프로그래머스

from collections import deque 
def solution(bridge_length, weight, truck_weights):
    bridgearr = deque([0] * bridge_length)// 다리에 올라갈 수 있는 트럭 수 만큼의 배열 0으로 초기화
    truck_weights = deque(truck_weights)
    answer = 0
    while (bridgearr): //brigdearr 배열이 비게 되면 While문 종료
        answer += 1 // 시간 + 1
        bridgearr.popleft() // bridgearr 배열의 맨 왼쪽 요소 제거
        if truck_weights: //대기하고있는 트럭이 존재하는 동안 if문 명령 시행
            if (sum(bridgearr) + truck_weights[0]) <= weight: //다리위의 트럭의 무게와 대기하고있는 첫번째 트럭의 무게가 weight 이하 일 시
                bridgearr.append(truck_weights.popleft())// 대기하고있는 트럭을 다리위에 적재
            else:// weight 보다 무거울 시
                bridgearr.append(0) // bridgearr 배열에 0추가

    return answer

다리 위를 지나갈 수 있는 트럭만큼 크기를 지정해주기 위해 다리 위 배열인 bridgearr을 주어진 bridge_length만큼 [0]으로 배열 초기화를 해주었음

 

위 코드로 제출했을 시 , 테스트 케이스 5에서 계속 시간 초과가 뜨는 현상이 발생함

 

처음에는 deque를 안쓰고 일반 스택을 이용하여 bridgearr.pop(0) 을 해주는 방식으로 코드를 작성 하였는데 , 이 부분에서 시간초과가 일어나는가 싶어 deque로 변경함

 

그래도 시간 초과가 계속 뜸

 

서칭을 통해 알아본 결과 sum(bridgearr) 에서 시간복잡도 문제가 생겼던 것 , sum()은 O(N)의 시간복잡도를 가짐

 

그래서 sum() 을 대체하여 다리위 트럭 무게의 합을 구하는 방법을 생각해본 결과 

from collections import deque 
def solution(bridge_length, weight, truck_weights):
    bridgearr = deque([0] * bridge_length)// 다리에 올라갈 수 있는 트럭 수 만큼의 배열 0으로 초기화
    truck_weights = deque(truck_weights)
    answer = 0
    s = 0 //다리 위 트럭무게를 합산한 결과를 넣은 변수 s 선언
    while (bridgearr): //brigdearr 배열이 비게 되면 While문 종료
        answer += 1 // 시간 + 1
        s -= bridgearr.popleft() // bridgearr 배열의 맨 왼쪽 요소 제거 , 다리 위 트럭 무게 합산
        if truck_weights: //대기하고있는 트럭이 존재하는 동안 if문 명령 시행
            if (s + truck_weights[0]) <= weight: //다리위의 트럭의 무게와 대기하고있는 첫번째 트럭의 무게가 weight 이하 일 시
                s += truck_weights[0] // s에 다리위에 새로 올라가게 된 트럭 무게 합산
                bridgearr.append(truck_weights.popleft())// 대기하고있는 트럭을 다리위에 적재
            else:// weight 보다 무거울 시
                bridgearr.append(0) // bridgearr 배열에 0추가

    return answer

위와 같이 s 라는 다리 위 트럭 무게의 총합을 담을 수 있는 변수를 선언하여 sum()을 대체 해주었음.