프로그래머스 고득점 Kit - 다리를 지나는 트럭

 

Problem

https://school.programmers.co.kr/learn/courses/30/parts/12081

프로그래머스

 

다리를 지나는 트럭

• 트럭 여러 대가 1차선 다리를 정해진 순서대로 건너려 한다.
• 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 한다.
• 다리의 길이는 bridge_length이며, 다리에는 트럭이 최대 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]	[]	[]

Input / Output Example

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

 

Solution

큐를 쓰면 쉽게 해결할 수 있다.

다리를 Queue로 정의하고, input으로 주어지는 대기 트럭도 큐로 만들면 편하게 풀 수 있다.

 

다리 위에 트럭이 있고, 트럭이 이제 내려와야 한다면 popleft 해주면 된다.

대기 트럭이 존재하고, 트럭을 다리 위에 올릴 수 있다면 append 해주면 된다.

 

do-while 문으로 작성했기에, 마지막에 다리 위에 아무것도 없고 대기 트럭도 없다면 반복문을 멈추게 해야 한다.

자세한 내용은 주석으로 달아뒀으니, 이해하는데 도움이 될 것이다.

Code

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0 	# 경과 시간
    bridge = deque() # 다리를 Queue로 선언
    truck_weights = deque(truck_weights) # 대기하는 트럭
    bridge_sum = 0 # 다리에 올라간 트럭 무게의 합
    while True: # do-while
        answer += 1 # 1초 증가
        if bridge_sum != 0 and (answer - bridge[0]['time'] == bridge_length): # 다리 위에 트럭이 있고, 트럭이 이제 내려와야 한다면
            data = bridge.popleft()
            bridge_sum -= data['weight']
        if len(truck_weights) > 0 and (bridge_sum + truck_weights[0]) <= weight: # 대기 트럭이 있고, 트럭을 다리에 올릴 수 있다면
            data = {
                'weight': truck_weights.popleft(),
                'time': answer
            }
            bridge_sum += data['weight']
            bridge.append(data)
        if bridge_sum == 0 and len(truck_weights) == 0: # 다리 위에 아무것도 없고, 대기 트럭도 없다면
            break
    return answer