[python][프로그래머스] 다리를 지나는 트럭_스택/큐

 

 

프로그래머스는 로고가 참 멋있다

 

 

 

 

 

 

https://programmers.co.kr/learn/courses/30/lessons/42583

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

 

 

 

< 트럭이 1초에 1 length만큼 갑니다 >

 

 

 

1. 다리의 길이만큼 리스트를 만든다.

 

2. 다리의 왼쪽이 빠진다.

 

3. 건널 트럭이 남았다면 

  3-1.  if ( 트럭이 갈수있다면) #이미 다리에 있는 트럭과 새로 갈 트럭의 무게가 weight보다 작다면

          트럭 리스트에서 빼서 다리 리스트에 넣는다. 

  3-2. else : # 갈수가 없다면

          다리 리스트 오른쪽에 0을 붙인다. 

 

 

 

---

코드 : 

 

<리스트 이용한 코드>

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = [0 for i in range(bridge_length)]
    
    while bridge : # 건널 트럭이 없어도 다리를 탄 트럭이 다리를 건너야하므로 
        answer += 1  # 1초가 흐름 # 더이상 새롭게 건널 트럭이 없어도 시간을 가야하므로 if문 밖에 있음 
        bridge.pop(0) # 가장 왼쪽이 나감 
        
        if truck_weights : # 건널 트럭이 남았다면 
            if sum(bridge) + truck_weights[0] <= weight : # 다리에 있는 트럭 무게 + 지금 갈까 하는 트럭 무게가 다리가 견딜 수 있는 무게보다 작다면 
                tmp = truck_weights.pop(0)
                bridge.append(tmp) # 다리를 건너라
            else : # 아니라면 
                bridge.append(0) # 시간만 가고 다리에는 아무것도 가지않도록  # 다리 길이 유지 
        
    return answer

 

 

 

[ 건널 트럭이 없더라도 다리에 탄 트럭이 다리를 건너야한다.

그러므로 while truck_weights가 아닌 while bridge를 한 후 내부에 if truck_weights를 둔다. ]

 

 

 

truck_weights 가 없으면 answer+=1, bridge.pop(0)을 이용해 

다리에 있는 차들을 한칸씩 앞으로 옮긴다. 

 

 

 

덱을 이용하면 데스트케이스 5번에서 시간초과가 발생한다.

이유는 sum이 O(n)을 갖고있기 때문이란다.

덱은 sum 계산이 list와 비교하여 느린가보다.

 

<덱을 이용한 코드 > :

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = deque([0 for i in range(bridge_length)])   
    sum_bridge = 0
    while bridge :
        answer+=1 
        tmp=bridge.popleft()
        sum_bridge -= tmp
        if truck_weights :
            if truck_weights[0] + sum_bridge <= weight :
                truck = truck_weights.pop(0)
                bridge.append(truck)
                sum_bridge+=truck
            else :
                bridge.append(0)
    return answer

 

그래서 이렇게 sum_bridge변수를 만들어 직접 빼고 더하면 시간초과 없이 통과할 수 있다.

 

 

 

---

 

 

 

 

 

배운점 : 

 

다리를 이렇게 생각할 수 도 있구나....멋져

다리에서 한칸 움직이면 앞쪽 다리가 뒤로 온다는 생각이 참 신박하다. 

 

 

 

 

 

참고 블로그 : 

https://velog.io/@henrynoowah/PYTHON-Programmers-%EB%8B%A4%EB%A6%AC%EB%A5%BC-%EC%A7%80%EB%82%98%EB%8A%94-%ED%8A%B8

[프로그래머스] 다리를 지나는 트럭 - PYTHON

https://yunaaaas.tistory.com/53

[Python - 프로그래머스 Level2] 다리를 지나는 트럭

 

 

복습 : 

 

✅ 20220616 

✅ 20220620

✅ 20220622

✅ 20220626

✅ 20220627

✅ 20220630

✅ 20220701