[프로그래머스][stack/queue] 다리를 지나는 트럭 python (200717)

https://velog.io/@filoscoder/Data-Structure-Stack-vs.-Queue

[Data Structure] Stack vs. Queue?

해당 문제는 먼저들어온 기차가 먼저 나가는 방식인 (First In First Out - FIFO) Queue 이다. 

Queue 는 리스트로 구현할 때 lista.pop(0) 으로 하면됨. --> 리스트 인덱스 0 번째가 빠짐. 

 

1. 문제 

 

문제 설명

 

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

 

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

 

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

 

 

제한 조건

 

• bridge_length는 1 이상 10,000 이하입니다.

• weight는 1 이상 10,000 이하입니다.

• truck_weights의 길이는 1 이상 10,000 이하입니다.

• 모든 트럭의 무게는 1 이상 weight 이하입니다.

 

입출력 예

 

bridge_length  / weight / truck_weights / return

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

 

 

2. 풀이 

 

0) 나의 화려한 오답  

 

def solution(bridge_length, weight, truck_weights):

    # 1. init
    wait_list = deque(truck_weights)
    bon_list = deque([])
    bon_truck_sum = 0
    f_list = deque([])
    total_time = 1

    # 2. loop
    while len(f_list) != len(truck_weights):
        if len(wait_list)>0:
            next_truck = wait_list[0]
            if bon_truck_sum + next_truck <= weight:
                now_truck = wait_list.popleft()
                bon_list.append([now_truck,2])

        total_time+=1 # 전체 시간 1증가
        # bon_list 리스트에 있는 트럭시간 -1 /  트럭시간 다된친구 삭제 /
        up_bon_list = []
        for t in bon_list:
            if t[1] > 1:
                up_bon_list.append([t[0], t[1] - 1])
                bon_truck_sum += t[0]
            else:
                f_list.append(t[0])
                bon_truck_sum -= t[0]
        bon_list = up_bon_list.copy()

    return total_time

런타임 에러 가 떴다 . 

현재 운행중인 트럭의 무게 합을 구하는 과정에서 오류가 발생했고 무한 루프에 빠져버린 것...

접근 방식 자체가 잘못되었다. 

 

 

 

1) pop 이용해서 풀기 ! 

def solution(bridge_length, weight, truck_weights):

	# 1. init 
    total_time = 0
    bridge = [0] * bridge_length

	# 2. loop
    while bridge:
        total_time += 1
        print(bridge)
        bridge.pop(0)
        if truck_weights:
            if sum(bridge) + truck_weights[0] <= weight:
                bridge.append(truck_weights.pop(0))
            else:
                bridge.append(0)

    return total_time

 

* 굳이 deque 가 아니라 pop(0) 쓰면 되었음 (머쓱) 

 

bridge_length = 2  // weight = 10  // truck_weights = [7,4,5,6] 인 경우 

Time 1 Bridge [0, 0]
Time 2 Bridge [0, 7]
Time 3 Bridge [7, 0]
Time 4 Bridge [0, 4]
Time 5 Bridge [4, 5]
Time 6 Bridge [5, 0]
Time 7 Bridge [0, 6]
Time 8 Bridge [6]

 

다리 길이만큼 리스트를 만들어 준 뒤 트럭 무게를 하나씩 넣고, 이동시켜주는 방식으로 

bridge 리스트의 요소가 다 빠져나가면 그때 time 이 멈춤  

 

 

 

3. 

문제 설명에서 나온대로 리스트 구현하느라 애먹었다.. (기어이 런타임에러) 

저렇게 간단히 풀수 있는 것을 (존빡)