[파이썬] 스택/큐 > 다리를 지나는 트럭

정답코드

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

 

이 문제는 트럭들이 일차선 다리를 건너는 데 걸리는 최소 시간을 계산하는 문제입니다. 다리의 길이, 다리가 견딜 수 있는 최대 무게, 그리고 트럭들의 무게가 주어졌을 때 모든 트럭이 다리를 건너는 데 필요한 시간을 구해야 합니다. 문제를 해결하기 위해 다음과 같은 접근 방식을 사용할 수 있습니다:

문제 해석 및 접근 방식

1. 다리의 길이와 무게 제한:
   • 다리에는 최대 bridge_length 대의 트럭이 동시에 있을 수 있습니다.
   • 다리 위의 트럭들의 총 무게는 weight를 초과할 수 없습니다.
2. 트럭의 상태 관리:
   • 대기 중인 트럭, 다리 위에 있는 트럭, 다리를 지난 트럭의 상태를 관리해야 합니다.
   • 각 트럭이 다리를 완전히 건널 때까지 걸리는 시간을 추적해야 합니다.
3. 시간의 흐름 시뮬레이션:
   • 매 초마다 트럭이 다리에 진입하고 다리 위의 트럭이 이동하며, 다리를 벗어나는 트럭을 처리합니다.

단계별 해결 방법

1. 초기 설정:
   • time 변수를 0으로 초기화하여 경과 시간을 추적합니다.
   • truck_weights를 deque로 변환하여 대기 트럭을 관리합니다.
   • bridge 큐를 초기화하여 다리 위에 있는 트럭들을 관리합니다. 이 큐의 길이는 bridge_length로 설정하고 초기 값을 0으로 채웁니다.
   • current_weight_on_bridge 변수를 0으로 초기화하여 현재 다리 위의 트럭들의 총 무게를 추적합니다.
2. 시뮬레이션 루프:
   • truck_weights가 비어 있지 않거나 bridge 큐에 트럭이 남아 있는 동안 반복합니다.
   • time을 1씩 증가시킵니다.
   • bridge 큐에서 맨 앞의 트럭을 제거하고, 해당 트럭의 무게를 current_weight_on_bridge에서 뺍니다.
   • 다음 트럭이 다리에 진입할 수 있는지 확인합니다. 다리 위의 총 무게와 다음 트럭의 무게 합이 weight를 초과하지 않는다면 트럭을 다리에 올리고, bridge 큐에 추가합니다. 그렇지 않다면 0을 추가하여 다리의 길이를 유지합니다.

코드 구현

다음은 이 논리를 구현한 코드입니다:

from collections import deque

def solution(bridge_length, weight, truck_weights):
    time = 0
    truck_weights = deque(truck_weights)
    bridge = deque([0] * bridge_length)  # 다리 위의 트럭 상태를 저장하는 큐
    current_weight_on_bridge = 0  # 현재 다리 위의 트럭들의 총 무게

    while truck_weights or current_weight_on_bridge > 0:
        time += 1
        # 다리에서 트럭 하나를 내보냄
        current_weight_on_bridge -= bridge.popleft()

        # 다음 트럭을 다리에 올릴 수 있는지 확인
        if truck_weights:
            if current_weight_on_bridge + truck_weights[0] <= weight:
                truck = truck_weights.popleft()
                bridge.append(truck)
                current_weight_on_bridge += truck
            else:
                bridge.append(0)  # 다리의 길이를 유지하기 위해 0을 추가

    return time

# 예제 테스트
print(solution(2, 10, [7, 4, 5, 6]))  # 출력: 8
print(solution(100, 100, [10]))  # 출력: 101
print(solution(100, 100, [10,10,10,10,10,10,10,10,10,10]))  # 출력: 110

코드 설명

• 초기화:
  • time은 경과 시간을 추적합니다.
  • truck_weights는 대기 중인 트럭의 무게를 관리하는 큐입니다.
  • bridge는 다리 위의 트럭을 관리하는 큐입니다. 초기 상태는 다리 길이만큼 0으로 채워집니다.
  • current_weight_on_bridge는 다리 위의 트럭들의 총 무게를 추적합니다.
• 시뮬레이션 루프:
  • 매 초마다 time을 증가시키고, 다리에서 트럭을 하나 제거합니다.
  • 다음 트럭이 다리에 진입할 수 있는지 확인하고, 가능하다면 트럭을 다리에 올립니다.
  • 트럭을 다리에 올릴 수 없다면 0을 추가하여 다리의 길이를 유지합니다.

이 코드는 트럭들이 다리를 건너는 데 걸리는 최소 시간을 정확히 계산할 수 있습니다.

코드연습과정 1 첫번째 코드

저는 스택/큐를 처음 배우고 나서 연습을 위해 바로 이 문제를 풀어보았습니다. 어찌어찌 코드를 반정도 짰는데 아무리 해도 다리 위의 트럭의 무게를 어떻게 구해야 할지 모르겠더라구요.

 

# 꼬꼬마코더가 짠 코드
from collections import deque
def solution(bridge_length, weight, truck_weights):
    time = 0
    truck_weights = deque(truck_weights)
    truck_on_the_bridge = deque([0]*bridge_length)
    
    while truck_weights:      

        if (sum(truck_on_the_bridge) + truck_weights[0]) <= weight:
            now_truck = truck_weights.popleft()
            truck_on_the_bridge.popleft()
            truck_on_the_bridge.append(now_truck)
        else:
            truck_on_the_bridge.popleft()
            truck_on_the_bridge.append(0)
        time += 1
    
    return time

print(solution(2, 10, [7, 4, 5, 6]))

다리 위의 트럭의 무게는 처음엔 0이고 7무게의 트럭을 다리로 보내니 7이 되죠. 그런데 7+4는 10이 넘으니 현재 다리 위에 있는 7무게의 트럭만 다리를 건너게 합니다. 그러면 다리 위의 트럭의 무게는 0이 되죠.

여기서 다리 위의 트럭의 무게를
truck_on_the_bridge =deque()
truck_on_the_bridge[0] 이렇게 하면 truck_on_the_bridge가 null이라서 에러가 나죠.

truck_on_the_bridge =deque([0] * bridge_length)
sum(truck_on_the_bridge) 하면? 

코드연습과정 2 두번째 코드

첫번째 테스트는 맞았지만 두 번째부터는 전혀 맞지 않았습니다.

왜냐면 두번째 문제는 truck_weights 에서 10무게의 트럭이 딱 하나인데 다리를 건너려고 할 때 이미 truck_weights 가 비어있기 때문에 while문을 계속 돌 수 없었습니다. 그렇다면 sum(truck_on_the_bridge)  >0 조건문을 또 추가해야겠네요.

 

그러나 제 코드는 또 문제에 봉착했습니다. truck_weights 가 없어도 truck_on_the_bridge의 트럭은 여전히 다리를 건너고 있었던 것입니다.

코드연습과정 3 세번째 코드

3일동안 밤마다 자기 전에 chatGPT가 준 답을 곰곰히 생각해보았습니다.

bridge = deque([0] * bridge_length)
current_weight_on_bridge -= bridge.popleft()

제 머리로는 도저히 이 생각은 못할 것 같습니다.
current_weight_on_bridge 는 current_weight_on_bridge 에서 현재 브릿지에 있는 트럭 뺀 값이다?????

다리는 그냥 올라갔다 내려오는 것이 아니라 정말로 bridge_length만큼 지나가야 하는 것이었습니다.

다시 문제로 돌아가서 정리를 하자면 이렇게 노란색으로 표시한 것처럼 다리를 bridge_length 만큼 공간을 만들어줘야 합니다.  bridge = deque([0] * bridge_length)

그리고 다리 위의 트럭들을 관리해야 했던거죠.

current_weight_on_bridge -= bridge.popleft()

from collections import deque
def solution(bridge_length, weight, truck_weights):
    time = 0
    truck_weights = deque(truck_weights)
    truck_on_the_bridge = deque([0]*bridge_length)
    current_weight_on_the_bridge = 0
    
    while truck_weights or (current_weight_on_the_bridge > 0):
        
        current_weight_on_the_bridge -= truck_on_the_bridge.popleft()
        
        if  current_weight_on_the_bridge + truck_weights[0] <= weight:
            now_truck = truck_weights.popleft()
            truck_on_the_bridge.append(now_truck)
            current_weight_on_the_bridge += now_truck
        else:
            truck_on_the_bridge.append(0)
            
        time += 1
    
    return time

다시 풀어보았지만 여전히 에러가 났고 어디에서 에러가 났는지 알 수 없기에 잘못된 습관대로 vscode를 돌려버렸습니다. 실제 시험장에서는 IDE환경을 주지 않기 때문에 어디서 에러가 났는지 디버깅할 수 없습니다. 그래서 되도록 예제를 하나씩 손으로 대입해가며 종이에 푸는 연습을 해야 합니다.

 

코드연습과정 4 네번째 코드

truck_weight[0] 인 경우에서 에러가 나네요. 그래서 다시 코드를 고쳤습니다.

# 최종 꼬꼬마코더 코드
from collections import deque
def solution(bridge_length, weight, truck_weights):
    time = 0
    truck_weights = deque(truck_weights)
    truck_on_the_bridge = deque([0]*bridge_length)
    current_weight_on_the_bridge = 0
    
    while truck_weights or (current_weight_on_the_bridge > 0):
        
        current_weight_on_the_bridge -= truck_on_the_bridge.popleft()
        
        if truck_weights:
            if  current_weight_on_the_bridge + truck_weights[0] <= weight:
                now_truck = truck_weights.popleft()
                truck_on_the_bridge.append(now_truck)
                current_weight_on_the_bridge += now_truck
            else:
                truck_on_the_bridge.append(0)
            
        time += 1
    
    return time

이 문제를 스스로 푸는데 무려 4일이 걸렸네요. 

첫 알고리즘 문제 풀이였는데 느낀 바가 있다면

1. vscode를 사용하면 안되겠습니다. 손으로 종이에 풉니다.

2. 한 문제를 내가 스스로 풀 수 있을 때까지 끝까지 붙잡고 풉니다.

3. 문제에 나와있는 주인공의 모든 상황을 변수로 구현하고 초기화합니다.

또 다음 문제 풀러 가봐야 겠네요!!!