[프로그래머스] 스택/큐 - 다리를 지나는 트럭 (파이썬)

프로그래머스 스택/큐 - 다리를 지나는 트럭, 문제 확인

문제 설명은 아래와 같다.

 

---

트럭 여러대가 일차선 다리를 정해진 순서대로 건넘

모든 트럭이 다리를 건너려면 몇초가 걸리는지 알아내야 함

트럭은 1초에 1만큼 움직임

다리길이 : bridge_length, 다리무게: weight (까지 견딤)

 

 

예를들어, 길이가 2이고 10kg 무게를 견디는 다리 있을 때, 무게가 [7,4,5,6]인 트럭이 순서대로 최단시간안에 다리를 건너려면 다음과 같고 모든 트럭이 다리를 지나기 위해 최소 8초가 걸린다. 

 

경과시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
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]	[]	[]

 

 

프로그래머스 스택/큐 - 다리를 지나는 트럭, 문제 풀이 (파이썬)

처음에는 위 표에나와있는 대로 다리를 지나는 중인 트럭 배열, 다리를 건너는 트럭 배열, 대기 트럭 배열을 전부 선언한 후 다리를 지난 트럭의 요소 수를 확인하는 방식으로 코드를 짰었는데 이게 잘 안됐다. 삽질을 엄청 많이 했다.

 

그래서 다리 길이만큼 다리를 0으로 채워준 후 일정 조건하에 트럭을 다리위에 올리거나 내리다가 다리위 트럭 무게의 총합이 0인 경우 멈추는 방식을 사용하기로 했다. (즉 다리 자체를 큐로 보는 것)

 

무한루프(시간의 흐름)를 돌면서 일단 트럭은 1초에 1만큼 움직이기 때문에 bridge에서 pop을 하나 해준다. 따라서 그만큼 밑에서 다시 append를 해줄 것이다. 만약 다리를 지나지 않은 트럭이 아직 있고 (len(trucks)>0), 제일 앞 트럭(trucks[0]) 무게와 다리위에 있는 트럭의 무게의 합이 허용범위라면 그다음 트럭을 trucks에서 pop해준 후 다리위에 올린다. 아니라면 트럭을 다리위에는 올리지 못하는 것인데 어쨌든 시간의 흐름상 트럭들이 1씩 움직여야 하므로 bridge에 0을 추가해준다. 

 

당연히 무한루프 내에서 time 값은 1씩 계속 증가된다. 마지막으로 다리위 총합이 0이라면 무한루프를 종료하게 된다. 

 

def solution(bridge_len, weight, trucks):
    bridge=[0 for _ in range(bridge_len)] #다리 0으로 초기화
    time=0
    
    while 1: #시간의 흐름(초단위) 
        bridge.pop(0) #다리 앞부분 요소 빼냄(밑에서 조건문에 따라 0또는 트럭을 추가)
        
        #대기큐에 있는 첫번째 트럭 무게와 다리위에 있는 트럭 무게의 합이 허용범위라면 트럭을 다리위에 올림
        if len(trucks)>0 and sum(bridge)+trucks[0]<=weight: 
            bridge.append(trucks.pop(0)) 
            
        #아니라면 0을 다리위에
        else:
            bridge.append(0) 
            
         #다리위 총합이 0이면 멈춤    
        if len(trucks)==0 and sum(bridge)==0:
            break
        time+=1
    return time+1

 

 

아래를 예로 들어보자.

 

bidge_length	weight	truck_weights	return
2	10	[7,4,5,6]	8

 

 

time을 기준으로 아래와 같이 bridge, truck이 구성되며 마지막 time==7일 때, bridge : [0,0], truck : []이 된다. time은 0부터 시작했으므로 +1한 값을 리턴해주면 8이 된다.

 

---

init)

bridge : [0,0]

truck : [7,4,6,5]

 

time==0)

bridge : [7,0] #무게 7인 트럭이 다리를 지남

truck : [4,6,5]

 

time==1)

bridge : [0,7] #무게 4인 트럭이 다리에 올라오면 11이 되므로 안됨

truck : [4,6,5]

 

time==2)

bridge : [4,0] #무게 7인 트럭이 다리를 전부 지나고 무게 4인 트럭이 올라옴

truck : [6,5]

 

time==3)

bridge : [6,4] #무게 6인 트럭이 또 올라와도 허용 무게 내임

truck : [5]

 

time==4)

bridge : [0,6] #무게 4인 트럭이 다리를 전부 지남

truck : [5]

 

time==5)

bridge : [5,0] #무게 6인 트럭이 다리를 전부 지나고 무게 5인 트럭이 올라옴 

truck : []

 

time==6)

bridge : [0,5] #무게 5인 트럭이 다리를 지나는 중

truck : []

 

time==7)

bridge : [0,0] #마지막 트럭까지 다리를 전부 지남 (다리위의 무게 총합이 0이고 truck 배열 길이가 0)

truck : []

 

 

그런데 채점 테스트케이스에서 테스트5가 시간 초과가 떴다.

 

 

 

5번 테스트만 시간 초과가 뜬다는 질문글의 답변을 보니 sum이 문제인 것 같았다. 다시보니 내 코드에 sum(bridge)를 하는 부분만 2번 이있다.

 

 

 

따라서 bridge에 pop과 append를 해주는 부분에서 다리무게를 계산해주고 sum(bridge) 대신에 해당 계산 결과가 담긴 변수 (sum_bridge)로 대체해주었다. 

 

def solution(bridge_len, weight, trucks):
    time=0; sum_bridge=0
    bridge=[0 for _ in range(bridge_len)]
    
    while 1:
        tmp=bridge.pop(0)
        sum_bridge-=tmp #다리무게계산
        if len(trucks)!=0 and sum_bridge+trucks[0]<=weight: 
            tmp=trucks.pop(0)
            bridge.append(tmp) 
            sum_bridge+=tmp #다리무게계산
        else:
            bridge.append(0)
        if len(trucks)==0 and sum_bridge==0:
            break
        time+=1
    return time+1

 

 

테스트케이스 4만 봐도 748ms이던게 14ms이다.

 

 

 

훨씬 빠르게 모든 테스트 케이스를 통과할 수 있게됐다 :)