[프로그래머스] 트럭을 지나는 다리

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

 

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 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_lengthweighttruck_weightsreturn

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

 

 

1. 풀이

 

이해하는데 시간이 좀 걸린 문제이다.

 

길이와 무게가 정해진 다리가 있고, 무게를 넘지 않는 선에서 대기 트럭들이 이동을 하는 문제이다.

 

좀 고생을 하다가 스터디를 하는 분들이 deque라는 얘기를 하시길래 찾아보고 해결할 수 있었다.

 

 

Deque

• 일반적인 queue는 FIFO, 한 방향으로만 데이터 입출력을 가능하게한다
• Deque는 양방향으로 데이터를 입출력 가능하게 해준다.
• 일반적인 리스트는 데이터를 POP()한 뒤, 리스트를 재정렬해야하지만 Deque는 양방향 입출력이 가능하므로 이 과정이 필요가 없어진다.

>>> deq.appendleft(10)
>>> deq.append(0)
>>> deq.appendleft(20)
>>> deq
deque([20, 10, 0])
>>> deq.popleft()
20

이런식으로 데이터를 넣는 방향과 뺴는 방향을 정할 수 있다.

 

이를 통해 코드를 구현해보았다.

from collections import deque
def solution(bridge_length, weight, truck_weights):
    truck_weights = deque(truck_weights)    # 리스트는 앞의 데이터를 pop 뒤의 데이터를 쉬프트해야하지만 디큐는 그런것들을 처리해준다.
    bridge = deque([0]*bridge_length)       # 다리를 건더는 트럭
    time = 0                                # 시간
    bridge_weight = 0                       # 다리 위의 무게 설정

우선 대기트럭의 무게를 deque설정을 해준다.

 

그리고 bridge_weight, 다리 위의 무게를 0으로 설정한다.

 

    while len(bridge) != 0:
        out = bridge.popleft()		# 다리를 나가는 트럭
        bridge_weight -= out
        time += 1

우선 다리위으 트럭이 한대도 없을 떄 까지 while문을 실행한다.

 

        if truck_weights:                                   # 대기 트럭이 존재한다면
            if bridge_weight + truck_weights[0] <= weight:  # 다리위의 무게와 대기트럭 첫번째의 무게의 합이 다리 무게보다 작다면 이동가능
                go = truck_weights.popleft()                # 대기트럭을 옮김
                bridge_weight += go                         # 다리무게에 대기트럭을 올림
                bridge.append(go)                           # ㄷ다리를 건너는 트럭에 올라간 트럭 옮김
            else:
                bridge.append(0)							# if문이 성립하지 않을 경우, 이 문장이 없다면 bridge리스트 값이 []이 될 수 있다.
    return time

다리 길이 : 2 / 제한 무게 : 10 / 대기트럭: [7,4,5,6]  

1.

다리 :  ([0, 0])
다리를 나간 트럭 : 0
현재 다리의 무게 : 0 시간 : 1, 대기 트럭 : ([7, 4, 5, 6]) 
'현재 다리 무게0 + 대기 트럭 첫번째 트럭 무게7 > weight10'
대기 트럭 : deque([4, 5, 6]) 올라간 트럭 : 7 
현재 다리의 무게 :  7
다리 :  ([0, 7])

2.

다리 :  ([0, 7])
다리를 나간 트럭 : 0
현재 다리의 무게 : 7 시간 : 2, 대기 트럭 : ([4, 5, 6]) 
다리 :  ([7, 0])

3.

다리 :  deque([7, 0])
다리를 나간 트럭 : 7
현재 다리의 무게 : 0 시간 : 3, 대기 트럭 : deque([4, 5, 6]) 
'현재 다리 무게0 + 대기 트럭 첫번째 트럭 무게4 > weight10'
대기 트럭 : deque([5, 6]) 올라간 트럭 : 4 
현재 다리의 무게 :  4
다리 :  deque([0, 4])

 

이런식으로 진행이 되는 것을 알 수 있다.

 

전체코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    truck_weights = deque(truck_weights) 
    bridge = deque([0]*bridge_length)      
    time = 0                               
    bridge_weight = 0                       

    while len(bridge) != 0:
      
        out = bridge.popleft()
        bridge_weight -= out
        time += 1
        
        if truck_weights:                                  
            if bridge_weight + truck_weights[0] <= weight:  
                go = truck_weights.popleft()                # 대기트럭을 옮김               
                bridge_weight += go                                      
                bridge.append(go)                           
            else:
                bridge.append(0)
    return time

if __name__ == '__main__':
    solution(2,10,[7,4,5,6])

 

# 스터디 멤버분들의 조언이 없었다면못풀었을듯... 나중에 다시 해봐야겠다