[programmers] 다리를 지나는 트럭

wonyu·2022년 4월 16일
0

algorithm

목록 보기
25/25

문제 링크

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

풀이 방법

푸는 것보다 문제를 이해하는 데에 더 오래 걸렸던 문제다.
우선 대기 중인 트럭, 다리를 건너는 트럭은 queue 형태로 먼저 들어온 순서대로 나갈 수 있다. 그리고 내가 이해한 다리를 건너는 핵심 조건 2가지는 아래와 같다.

  1. 한 트럭이 다리를 건너는 데에는 bridge_length 초 소요됨
  2. 1초당 한 트럭만 다리에 오르거나 다리에서 내려갈 수 있음

따라서 이 조건을 따르면서 while문을 통해 1초씩 시간 체크를 한다. 그리고 on_bridge, truck_weights 리스트가 둘 다 비어있게 되는 초에 반복문을 종료하고 해당 시간을 리턴한다.

코드

def solution(bridge_length, weight, truck_weights):
    sec = 0
    on_bridge = []
    truck_weights = truck_weights[::-1]     # [-1] 요소를 pop 하기 위해 reverse 해서 사용

    # 대기 중이거나 다리를 건너는 트럭이 있을 경우
    while truck_weights or on_bridge:
        sec += 1
        # 다리를 건너는 트럭이 있고, 가장 첫 트럭이 다리를 다 건넜다면 pop
        if on_bridge and on_bridge[0][1] <= sec:
            on_bridge.pop(0)
        # 대기 중인 트럭이 있고, 다리 길이 및 무게 조건을 만족했을 경우 append
        if truck_weights and len(on_bridge) + 1 <= bridge_length and sum([truck[0] for truck in on_bridge]) + truck_weights[-1] <= weight:
            on_bridge.append([truck_weights.pop(), sec + bridge_length])

    return sec

0개의 댓글