[프로그래머스] 다리를 지나는 트럭 (Lv2, Python3)

문제

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

두 가지 가정이 빠져있음 🤬

1. 트럭의 속도는 1 per sec
2. (무게에 여유가 있더라도) 한 턴에 대기열 맨 앞 트럭 한 대만 올라갈 수 있다.

풀이

아이디어

• 무한루프 돌리면서 time += 1
• 매 loop 마다
  • 이동중인 트럭 한 칸씩 앞으로 전진
  • 무게 여유 있을 때 대기중인 트럭 출발 (한 loop에 한 대씩 만)
• 대기중인 트럭 없고, 이동중인 트럭도 없으면 loop 종료

solution.py

from collections import deque

def solution(bridge_length, weight, truck_weights):
    
    truck_weights = deque(truck_weights)  # 넣고 빼고 할 때 시간복잡도 낮추기 위해 deque로 선언
    
    cur_truck_weight_lst = deque()  # 지금 다리 위에 있는 트럭들의 무게
    cur_truck_loc_lst = deque()  # 지금 다리 위에 있는 트럭들의 위치
    time = 0

    while True:
        time += 1

        # 다리 위에 있는 트럭들 한 칸씩 앞으로 이동
        for idx, val in enumerate(cur_truck_loc_lst):
            cur_truck_loc_lst[idx] = val+1

        # 가장 앞에 있는 트럭이 끝까지 건넜는지 확인해서, 건넜으면 cur에서 제거
            # 트럭은 한 대 씩만 올라오고, 속도는 1로 같기 때문에 여러 대가 동시에 도착하는 경우는 없음
        if cur_truck_loc_lst and (cur_truck_loc_lst[0] == bridge_length):
            cur_truck_weight_lst.popleft()
            cur_truck_loc_lst.popleft()

        # 도착한 트럭을 제외한 나머지 트럭 무게의 총합
        cur_weight_sum = sum(cur_truck_weight_lst)

        # 대기중인 트럭이 있고, 현재 무게가 허용무게보다 가벼울 경우
        if truck_weights and (cur_weight_sum < weight):
            next_truck_weight = truck_weights.popleft()
            
            # 다음 순서 트럭이 올라가도 허용무게 이하라면, 올림
            if cur_weight_sum + next_truck_weight <= weight:
                cur_truck_weight_lst.append(next_truck_weight)
                cur_truck_loc_lst.append(0) 
            
            # 아니면 다시 대기
            else : truck_weights.appendleft(next_truck_weight)
    
        # 대기중이거나 다리 위에 트럭이 하나도 없을 경우 종료
        if not truck_weights and not cur_truck_loc_lst:
            break
            
    return time

수행결과

더 좋은 풀이

아이디어

• 다리 길이 만큼의 deque 를 만들고, 다리 위의 각 자리에 트럭을 배치, 1초마다 re-indexing하여 한 칸씩 앞으로 옮김

  다리를 deque로, index로 현재 건너고 있는 트럭의 위치를 표현하는 방식 🤭
  index : 0 이면 다리의 가장 끝 (다음 loop에 다리 다 건넘)

• truck_weights 앞에서부터 하나씩 빼올 때 시간복잡도 낮추기 위해 reverse 시킨 후에 pop() 해서 하나씩 뺌

solution.py

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque(0 for _ in range(bridge_length))
    total_weight = 0
    step = 0
    truck_weights.reverse()

    while truck_weights:
        total_weight -= bridge.popleft()
        if total_weight + truck_weights[-1] > weight:
            bridge.append(0)
        else:
            truck = truck_weights.pop()
            bridge.append(truck)
            total_weight += truck
        step += 1

    step += bridge_length

    return step