코딩테스트 연습> 스택/큐> 다리를 지나는 트럭

 

<문제링크: https://programmers.co.kr/learn/courses/30/lessons/42583>

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

 

문제설명: 다리를 지나려고 대기중인 트럭들의 배열인 truck_weights가 주어지고, 다리가 지탱할 수 있는 트럭의 무게 weight가 주어진다. 그리고 다리의 길이는 bridge_length로 주어지는데 트럭이 움직이는 이동거리라고 볼 수 있다.

 

다리위의 트럭의 무게를 보면서 트럭이 다리를 지날 수 있는경우와 앞의 트럭들이 다 빠질 때까지 기달리는 로직을 적절히 짜서 문제를 해결할 수 있다. 그러면서 다리를 건너는 트럭들이 한칸씩 움직이는 이동거리의 누적합을 구해 맨 처음 다리를 지나는 트럭의 이동거리를 정답으로 return하면 된다.

 

[1차 시도]

def solution(bridge_length, weight, truck_weights):
    on = []
    fin = []
    v = [0]*len(truck_weights)
    h=0
    while fin != truck_weights:
        if h<len(truck_weights):
            if sum(on)+truck_weights[h] <= weight:
                on.append(truck_weights[h])
                h+=1
        for i in range(h):
            v[i]+=1
        if bridge_length in v:
            fin.append(on.pop(0))
    return v[0]+1

 

풀이: 먼저 다리를 지나고 있는 트럭을 담을 on 배열과, 다리를 다 지난 트럭을 담을 fin 배열을 만들었다. 그리고 트럭들의 움직이며 누적되는 합을 구하기 위해 트럭개수만큼 0으로 채운 v배열을 만들었다.

 

while문을 돌리는 기준은 fin배열이 처음주어지는 truck_weights와 같아질 때까지이다. 즉 모든 트럭이 다리를 다 건넜을 경우 반복문을 중단한다.

 

트럭이 순서대로 빠져나가면서 해당 트럭의 이동누적 값을 증가시키기 위해 트럭이 담긴 truck_weights 배열의 인덱스를 저장하기 위한 변수를 0을 while문 위에서 만들어 주었다. h가 아래에서 증가하는데 트럭의 개수(truck_weights의 길이)보다 작을 경우, 이동 중 트럭의 배열 on의 합과 이동할 차례가 된 트럭의 합이 다리가 지탱할 수 있는 무게라면, 다리를 지나갈 수 있는 트럭이므로 on배열에 현재 위치의 트럭을 추가한다. 그리고 다음 트럭을 꺼내기 위해 현위치를 +1해준다.

 

이후 현재 위치의 트럭 인덱스로 돌면서 v배열의 값을 1씩 증가시킨다. 현재 위치의 트럭 이전에 출발한 트럭들 모두 1씩 이동 혹은 다리를 다 지났기 때문에 출발로부터 경과시간이 1씩 지났음을 표시하는 것이다.

 

v배열의 재조정이 끝났다면, 다리길이(bridge_length)와 경과 시간이 일치한 트럭, 즉 다리를 다 빠져나온 트럭을 의미하므로 on에서 pop을 해주어 fin에 추가해준다.

 

*문제 첫 번째 예시의 경우, 트럭의 이동 흐름을 다음과 같이 볼 수 있다.

 

경과시간	다리 지나는 트럭(fin)	다리 지나는 중(on)	대기트럭(truck_weights)	트럭 이동누적값(v)
0	[]	[]	[7,4,5,6]	[0,0,0,0]
1	[]	[7]	[4,5,6]	[1,0,0,0]
2	[]	[7]	[4,5,6]	[2,0,0,0]
3	[7]	[4]	[5,6]	[3,1,0,0]
4	[7]	[4,5]	[6]	[4,2,1,0]
5	[7,4]	[5]	[6]	[5,3,2,0]
6	[7,4,5]	[6]	[]	[6,4,3,1]
7	[7,4,5]	[6]	[]	[7,5,4,2]
8	[7,4,5,6]	[]	[]	[8,6,5,3]

위의 코드로 실행하면, 마지막 트럭이 on에서 빠져나와 fin으로 들어가는 과정은(경과시간 8) 포함되지 않으므로 최종적으로 v의 첫번째 인덱스(첫 트럭이 출발하고 모든 트럭이 다리를 건널때까지 경과 시간)에 +1한 값으로 return 하면 된다.

 

 

채첨결과: 정확성과 효율성 테스트 모두 잘 통과하지만 테스트 5의 경우 (9356.36ms, 10.8MB)의 기록으로 시간이 매우 많이 걸린다는 것을 알 수 있다.

 

 

해결방법: 해당 코드는 while문 밑에 if문으로 조건을 걸어 마지막 대기트럭이 빠져나올 때까지만 본다. 즉 마지막 트럭이 빠져나와 bridge_length만큼 이동하는 동안은 else로 빠져나와 for문을 돌며 v배열의 트럭들의 위치를 증가시킨다. 이는 만약 bfidge_length가 최고 길이 10,000이라면, 무의마한 10,000을 수행해야 하므로, 마지막 트럭이 빠져나왔을 때는 바로 다리길이만큼 경과 시간을 더해주면 된다. 이때 경과시간의 기준은 첫 번째 트럭이기 때문에 v[0]에 더해주면 된다.

 

 

[2차 시도]

def solution(bridge_length, weight, truck_weights):
    on = []
    fin = []
    v = [0]*len(truck_weights)
    h=0
    while fin != truck_weights:
        if h<len(truck_weights):
            if sum(on)+truck_weights[h] <= weight:
                on.append(truck_weights[h])
                h+=1
        for i in range(h):
            v[i]+=1
        if bridge_length in v:
            fin.append(on.pop(0))
        if h==len(truck_weights):
            v[0] += bridge_length
            return v[0]

 

풀이: if문에서 else에 해당해 빠져나온 뒤 for문과 if문을 거쳐 h가 트럭의 개수와 일치하다면, 즉, 모든 트럭이 대기목록에서 다 빠져나왔다면, 현재 v배열에 있는 첫 번째 트럭의 이동거리에 다리길이만큼 더해주고 바로 return 한다.

 

 

채첨결과: 이제와서 보니 아주 약간 미묘하게 줄어들었다. 테스트의 시간을 아주 조금이나 더 줄여볼 수 있었다.