[프로그래머스] [Level 2] [스택/큐] 다리를 지나는 트럭

다리를 지나는 트럭

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

 

 

• 내 풀이
  • 앞선 트럭이 없는 경우: 다리 길이만큼 시간 소요
  • 앞선 트럭이 있는 경우: 앞선 트럭이 다리를 지나친 이후의 거리만큼 시간 추가
  • 맨마지막 트럭의 경우: 다리 길이 지난 후 나올 시간 +1 추가

from collections import deque
def solution(bridge_length, weight, truck_weights):
    
    queue=deque(truck_weights)
    list=deque()
    count=[]
    num=0
    l_weight=0
    answer=0
    while queue:
        if num!=bridge_length:
            if l_weight+queue[0]<=weight:
                t=queue.popleft()
                list.append(t)
                l_weight+=t
                count.append(0)
                if num:
                    answer+=count[-2] #앞서 건너는 트럭과의 거리 차이만큼 시간 소요
                else:
                    answer+=bridge_length #다리 제일 앞에 있는 트럭이 소요할 시간
                    
                num+=1
        for i in range(len(count)):
            count[i]+=1

        if count[0]==bridge_length:
            num-=1
            t=list.popleft()
            l_weight-=t
            del count[0]
            
    answer+=1 #맨 마지막 트럭이 나오는 시간
        
    return answer

print(solution(2, 10, [7,4,5,6]))
print(solution(100, 100, [10]))
print(solution(100, 100, [10,10,10,10,10,10,10,10,10,10]))
#결과 
8
101
110

 

 

• 다른 사람 풀이
  • 지나갈 트럭과 트럭무게를 한 번에 처리할 수 있는 방법 
    • 다리 길이 만큼 0을 큐(bridge)에 넣은 후
    • 트럭이 올라갈 수 있으면 트럭 무게를 큐에 넣고 아니면 0을 삽입
    • 큐에서 값을 pop하면서 트럭 이동

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque(0 for _ in range(bridge_length))
    total_weight = 0
    step = 0
    truck_weights.reverse()

    while truck_weights:
        total_weight -= bridge.popleft()
        if total_weight + truck_weights[-1] > weight:
            bridge.append(0)
        else:
            truck = truck_weights.pop()
            bridge.append(truck)
            total_weight += truck
        step += 1

    step += bridge_length

    return step