Lv2. 다리를 지나는 트럭 (스택/큐) [X]

문제 출처 : programmers.co.kr/learn/courses/30/lessons/42583

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

1. 문제 이해

트럭은 1초에 1만큼 움직임

다리 길이는 bridge_length

다리는 weight까지 견딤 (트럭이 다리에 완전히 오른 경우만 고려)

모든 트럭이 다리를 건너려면 최소 몇초가 걸리는지 리턴

 

bridge_length는 10000이하

weight도 10000 이하

truck_weights도 10000이하

 

2. 풀이 계획

트럭의 개수만큼 반복

트럭의 무게의 총합이 weight보다 작으면 트럭이 다리를 건널 수 있다.

 

for truck_weights

큐의 길이가 length 이거나 현재 트럭의 무게와 큐의 원소의 합이 weight 초과이면

큐 모두 pop -> ans += length, 큐에 원소 추가

그렇지않으면 큐에 원소 넣기, ans += 1

큐가 비어있지 않으면 ans += length

 

3. 구현

# 틀린 코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    ans = 0
    q = deque([])
    
    for t in truck_weights :
        if len(q) >= bridge_length or (sum(q) + t) > weight :
            q = deque([t])
            ans += bridge_length
        else :
            q.append(t)
            ans += 1
    
    if q :
        ans += bridge_length
    return ans

 

이렇게 풀면 테스트케이스는 맞지만

bridge_length가 10이고 weight가 10일 때 7 3 6 4 가 들어온다고 했을 때

7 3 따로 6 4 따로 계산된다. (7 3 -> 3 6 -> 6 4가 돼야되는데 7 3 -> 6 4 로 돼서 안된다)

 

4. 검토 및 개선

# 9628 ms

def solution(bridge_length, weight, truck_weights):
    answer = 0
    q = [0] * bridge_length # 다리 길이만큼의 리스트 생성
    
    while q :
        q.pop(0) # 왼쪽으로 한칸씩 이동
        answer += 1
        if truck_weights :
            if sum(q) + truck_weights[0] > weight :
                q.append(0)
            else :
                q.append(truck_weights.pop(0))
    return answer

 

위의 풀이에서 q를 deque로 만들면 더 빨라질 줄 알았는데 시간초과가 난다 ...

아무래도 계속해서 sum을 구하는 것 때문에 시간이 오래걸리는 듯하다.

 

# 284 ms

def solution(bridge_length, weight, truck_weights):
    answer = 0
    q = [0] * bridge_length
    total_weight= 0
    
    while q :
        truck = q.pop(0)
        total_weight -= truck
        answer += 1
        
        if truck_weights :
            if total_weight + truck_weights[0] > weight :
                q.append(0)
            else :
                truck = truck_weights.pop(0)
                q.append(truck)
                total_weight += truck
    return answer

 

sum을 매번 구하지않고 total_weight라는 변수를 이용해서 현재까지의 sum을 구현했다.

 

# 49 ms

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque([0] * bridge_length)
    total_weight = 0
    sec = 0
    truck_weights = truck_weights[::-1] #truck_weights.reverse()
    
    while truck_weights :
        total_weight -= bridge.popleft()
        sec += 1
        
        if total_weight + truck_weights[-1] > weight :
            bridge.append(0)
        else :
            truck = truck_weights.pop()
            bridge.append(truck)
            total_weight += truck
            
    if bridge :
        sec += bridge_length # 마지막 원소가 들어가고 다리길이만큼 이동하면 끝나기때문
        
    return sec

 

pop(0)의 시간복잡도는 O(n)이지만 (배열의 첫번째 원소를 빼고 나머지를 재배치해야되기 때문)

 

pop()과 deque의 popleft()의 시간복잡도는 O(1)이므로

배열을 거꾸로 만들고 pop()을 사용하거나 deque를 사용하여 큐로만들어 popleft하는 것이 더 빠르다 !!