코딩테스트 준비 - 프로그래머스: 다리를 지나는 트럭 풀이/상세 설명/스택과 큐 (파이썬)

---

다리를 지나는 트럭 풀이

---

문제풀러가기

https://programmers.co.kr/learn/courses/30/lessons/42583?language=python3 

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

---

문제 분석

1. 스택과 큐를 활용하면 된다.

2. 시간을 세는 과정은 아래 그림과 같다.

 

---

코드1

def solution(bridge_length, weight, truck_weights):
    time=0
    bridge=[0]*bridge_length
    while bridge:
        time+=1
        bridge.pop(0)
        if truck_weights:
            if (sum(bridge)+truck_weights[0])<=weight:
                bridge.append(truck_weights.pop(0))
            else:
                bridge.append(0)
    return time

* 일반적으로 생각할 수 있는 로직

* 효율성이 매우 낮다

코드2

*코드1과 같은 로직이지만, 코드1을 조금 더 다듬어서 효율성을 높였다.

from collections import deque
def solution(bridge_length, weight, truck_weights):
    truck_weights=truck_weights.reverse()
    time=0
    bridge=deque([0]*bridge_length)
    rs=0
    while bridge:
        time+=1
        rs-=bridge.popleft()
        if truck_weights:
            if (rs+truck_weights[0])<=weight:
                rs+=truck_weights[0]
                bridge.append(truck_weights.pop())
            else:
                bridge.append(0)   
    return time

* sum을 없애주니 확실히 시간이 더 줄었다.

---

코드 풀이

from collections import deque
def solution(bridge_length, weight, truck_weights):
    truck_weights=truck_weights.reverse() #pop(0)말고 바로 pop()을 사용하기 위해 뒤집음
    time=0
    bridge=deque([0]*bridge_length) #다리 길이만큼 공간을 만들어줌.
    rs=0  # 다리위의 트럭무게를 표시하기 위한 변수
    while bridge: 
        time+=1 #옆으로 트럭을 하나씩 넣을때마다 time+1을 해줌
        rs-=bridge.popleft() 
        if truck_weights:
            if (rs+truck_weights[0])<=weight:
                rs+=truck_weights[0]
                bridge.append(truck_weights.pop())
            else:
                bridge.append(0) #옆에 0으로 채워주면, 트럭이 점점 왼쪽으로 밀려나게됨.
    return time