[Python] 프로그래머스 다리를 지나는 트럭

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

프로그래머스

 

풀이

트럭 여러대(truck_weights)가 다리를 지날때 걸리는 총 시간을 구하려 합니다. 다리에는 최대 bridge_length만큼의 트럭이 올라갈 수 있으며, 올라간 트럭의 무게는 weight 이하여야 합니다.

 

트럭이 다리에 진입한 시간을 기록하고 그때 트럭의 무게를 기록하여,

다음 트럭을 진입시킬 수 있는지와 트럭이 언제 다리를 빠져나오는지 판단하는 알고리즘을 구현하였습니다.  다리위에 트럭이 없다면 모두 지나간 것으로 판단하고 답을 리턴합니다.

 

다리 진입 시간은 in_time에 기록하고, 다리 위 트럭의 총 무게는 curr_w에 기록합니다.

1. 빠져나갈 수 있는 트럭이 있는지 판단하고,

2. 다리에 다음 트럭을 올릴 수 있는지 판단합니다.

 

1의 경우, 현재 시간과 in_time의 가장 앞 원소의 차이가 bridge_length라면 in_time과 curr_w에서 가장 앞 원소를 빼줍니다.

2의 경우 curr_w의 합과 대기중인 가장 앞 트럭의 무게를 합하여 weight 보다 작거나 같다면 curr_w에 추가해주고 truck_weights 에서는 빼줍니다. 그리고 그때의 시간을 in_time에 넣어줍니다.

 

참고

아래 풀이 2는 q를 다리 길이만큼 초기화 하여, 시간을 따로 기록하지 않고 문제를 해결하는 방법입니다. 시간을 따로 기록하지 않아도 되는 장점이 있지만, q를 고정길이로 초기화 하여 기존 풀이보다 3배정도 시간이 더 걸립니다. 

def solution(bridge_length, weight, truck_weights):
    answer = 0
    in_time = [] # 트럭 진입 시간
    curr_w = [] # 다리 위 트럭
    time = 1
    
    while True:
        if in_time:
            if time - in_time[0] >= bridge_length:
                in_time.pop(0)
                curr_w.pop(0) 
            
        # curr_w가 weight 이하인 경우 현재 시간 큐에 넣기
        if truck_weights:
            if sum(curr_w)+truck_weights[0] <= weight:
                curr_w.append(truck_weights.pop(0)) 
                in_time.append(time)
        
        if not curr_w:
            answer = time
            break
            
        time += 1
        
    return answer

 

풀이2

def solution(bridge_length, weight, truck_weights):
    q=[0]*bridge_length
    sec=0
    curr_w = 0
    while q:
        sec+=1
        curr_w -= q.pop(0)
        if truck_weights:
            if curr_w+truck_weights[0]<=weight:
                curr_w += truck_weights[0]
                q.append(truck_weights.pop(0))
            else:
                q.append(0)
    return sec