[프로그래머스 lv 2] 다리를 지나는 트럭

사용 언어 - Python3

문제 - 다리를 지나는 트럭

프로그래머스

 

 

정답

다리 위에 있는 트럭의 위치를 알아야하는 스택/큐 문제 (정답 맞춘 여부 X)

정답 풀이 -  sum 연산은 O(N)으로 시간이 느리다. 한개의 테스트케이스에서 시간 초과로 오답!

1. 변수 정의

sec = 경과 시간 / q = bridge_length 다리길이만큼의 0 리스트 = 다리에 있는 트럭 입력받는 리스트

sec 경과시간은 한번

q.pop(0)로 리스트 맨 앞을 삭제한다.

 

2. 다리에 올라갈 수 있는 if문

현재 다리에 있는 트럭의 무게 합 sum(q) 과

들어가려는 트럭 무게 truck_weights[0]을 합한 값이

다리가 감당할 수 있는 weight보다 작거나 같아야

다리에 올라탈 수 있게 해준다. = q에 append한다.

예) truck_weights = [7,4,5,6], bridge = [0,0] 인 경우,

진짜 도로를 건너는 것처럼 q = [0,0] -> [0,7] -> [0,7] -> [7,0] , answer = 2 가 된다.

 

3. return answer

# 다른 사람의 풀이
def solution(bridge_length, weight, truck_weights):

    q=[0]*bridge_length
    sec=0
    
    while q:
        sec+=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

 

정답 풀이 -  위 풀이에 temp 변수 추가 & 큐 사용한 형태로 시간복잡도 관리!

1. from collections import deque

truck_weights와 truck_bridge를 deque로 만들어 poopleft()를 사용해준다.

 

2. temp = 0

temp -= truck_bridge_deque[0] 다리의 맨 앞에 있는 값을 뺀다. (맨 앞에 트럭이 없으면 0, 있으면 트럭의 무게)

temp += truck_weights_deque[0] 맨 앞에 있는 트럭 무게를 더한다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    
    answer = 0
    temp = 0
    
    truck_bridge_deque = deque(bridge_length * [0])
    truck_weights_deque = deque(truck_weights)
    
    while len(truck_bridge_deque):
        answer += 1
        temp -= truck_bridge_deque[0]
        truck_bridge_deque.popleft()
        if truck_weights_deque:
            if temp + truck_weights_deque[0] <= weight:
                temp += truck_weights_deque[0]
                truck_bridge_deque.append(truck_weights_deque.popleft())
            else:
                truck_bridge_deque.append(0)
    return answer

---

레퍼런스

• 정답 참고

[파이썬] 프로그래머스 - 다리를 지나는 트럭

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부