프로그래머스 Lv 2. 다리를 지나는 트럭

💡문제

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

| 입출력

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

 

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

| 입출력 예 설명

bridge_length	weight	truck_weights	return
2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

✏️ 내 풀이

from collections import deque
def solution(bridge_length, weight, truck_weights):
    #bridge_length:다리에 올라갈 수 있는 트럭수
    #weight: 다리가 견딜 수 있는 무게
    #truck_weights:트럭별 무게
    
    bridge=deque([0]*bridge_length)
    truck=deque(truck_weights)
    current_weight=0
    time=0
    
    while bridge:
        current_weight-=bridge.popleft()
        time+=1
        
        #대기 트럭이 남아있는 경우
        if truck:
            if current_weight+truck[0]<=weight:
                new_truck=truck.popleft()
                bridge.append(new_truck)
                current_weight+=new_truck
            else:
                bridge.append(0)
            
    return time

 

사실 저번에 풀었는데 다시 풀때마다 계속 틀렸었다

그래서 오늘은 오답을 적는거보다 코드 리뷰를 적어보려고 한다

 

이 문제의 핵심포인트는 큐(queue)를 이용하는 것이다

bridge=deque([0]*bridge_length)
truck=deque(truck_weights)
current_weight=0
time=0

 

list의 경우 인덱스 접근은 빠르지만 삽입/삭제가 느리다 (O(n))

왜나하면 pop(0)을 예로 들자면, 맨앞의 요소를 제거하고 나머지 요소들을 모두 왼쪽으로 한칸씩 이동해야한다

하지만 queue의 pop의 경우 해당 요소만 제거를 수행하기 때문에 나머지 요소들은 이동할 필요가 없다 (O(1))

while bridge:
	current_weight-=bridge.popleft()
	time+=1

 

또한 이 문제의 경우 다리가 빌때까지 수행해야한다

우리의 목표는 모든 트럭이 지나갈때까지의 시간을 구하는거니까!

그리고 처음으로 돌아오면 시간이 지나는거니까 popleft을 해주고 시간이 지났다니는 것을 check 해줘야한다

 

#대기 트럭이 남아있는 경우
if truck:
    if current_weight+truck[0]<=weight:
    new_truck=truck.popleft()
    bridge.append(new_truck)
    current_weight+=new_truck
else:
	bridge.append(0)

 

만약에 대기트럭이 남아있다면 하나를 먼저 꺼내서 최대무게보다 같거나 작은 체크를 해준다

만약에 조건에 충족한다면 하나를 꺼내서 다리에 올려준다

그리고 현재 무게를 업데이트해준다

조건에 충족하지 않으면 0을 넣어준다

 

이런 식으로 코드를 짠다면 정답으로 도달할것이다

 

🚀 해결 방법

1. 큐(deque)를 사용하여 다리를 관리
   • bridge를 deque([0] * bridge_length)로 초기화하여 다리 위 공간을 미리 만들어 놓는다.
   • 매 초마다 popleft()를 수행하여 트럭을 한 칸씩 이동시킨다.
2. 현재 다리 위 트럭들의 무게(current_weight)를 계속 추적
   • popleft()를 하면 다리에서 나가는 트럭의 무게를 current_weight에서 빼준다.
   • 새로운 트럭을 올릴 수 있는지 체크하고, 가능하면 append()하여 다리 위 트럭 목록을 갱신한다.
3. 시간(time)을 계속 증가시키면서 모든 트럭이 다리를 지나갈 때까지 반복
   • 마지막 트럭이 다리 끝까지 지나가면 종료한다.