programmers #다리를 지나는 트럭

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

 

 

def solution(bridge_length, weight, truck_weights):
    num = len(truck_weights)
    que = []   #[트럭, 다리 위 위치] 로 된 2차원 리스트
    timer = 0
    finish = []   #다리를 건넌 트럭들
    while len(finish) < num:
        timer += 1   #루프를 돌때마다 시간을 +1
        sum = 0   #다리 위에 있는 트럭들의 무게 합
        if que:
            for i in range(len(que)):
                if que[i][0] == 0:
                    continue
                
                que[i][1] += 1   #트럭을 앞으로 한칸 이동
                if que[i][1] > bridge_length:   #트럭이 이동한 거리가 다리 길이보다 길면
                    finish.append(que[i][0])    #다리 통과
                    que[i] = [0,0]              #큐(다리)를 초기화
                else:
                    sum += que[i][0]            #다음 트럭의 무게를 우선 계산(올릴지/말지)
            if truck_weights and (sum + truck_weights[0]) <= weight:  #무게가 가능하다면
                que.append([truck_weights.pop(0),1])   #큐에 추가
        else:   #큐(다리)가 비어 있을 때 
            if truck_weights:   #대기하는 트럭이 있다면  
                que.append([truck_weights.pop(0),1])   #큐(다리)에 트럭을 올리고 앞으로 거리1 이동
    return timer

우선 내가 이해한 바로 코드에 설명을 부여했다.

이 문제를 처음 접했을 때 가장 난감했던 부분은 시간을 어떻게 재야하는 것인가였는데 스택처럼 시간을 재는 변수를 추가하면 되었다. 그리고 스택/큐는 while문을 많이 활용하는 듯 하다. 그래서 while을 돌 때마다 타임을 늘리면 시간 계산이 가능하다.

 

그리고 2차원 리스트 [트럭, 위치]를 한꺼번에 생각하는 것이 코드를 간략하게 쓸 수 있는 좋은 아이디어같다.

다른 문제들보다 가장 직관적으로 이해할 수 있는 풀이라고 생각해서 이 코드를 외우는 것으로 공부했다.