[알고리즘 풀이] 프로그래머스 : 다리를 지나는 트럭, Level2(스택/큐)

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

알고리즘 연습 - 다리를 지나는 트럭 | 프로그래머스

1. 가장 앞에 있는 트럭을 뽑는다.

2. 다리에 있는 트럭을 확인한다.

3. 다리에 트럭이 없거나, 뽑은 트럭과 다리에 있는 트럭의 합이 weight 이하이면 다리를 트럭에 넣는다.

4. 1초마다 반복한다.

 

+ 트럭이 들어간지 다리의 길이만큼 지나면 빼낸다.

 

10분 정도 위의 내용을 생각해보고 코드로 구현해서 풀었다.

디버깅 과정은 생각보다 짧았고, 문제푸는데는 총 30분 정도 소요. 

 

아래는 풀이한 코드

def solution(bridge_length, weight, truck_weights):
    answer = 0 #시간
 
    t_list = [] # 트럭저장하는 큐 (리스트로 만듬) - 다리상황과 동일하다고 생각하면 됨
 
    # 트럭뽑는 함수
    for i in truck_weights :
        q_truck = i
        while q_truck != 0 : #트럭이 빠질때까지 확인하기 위해서
            if len(t_list) == bridge_length : #t_list의 길이가 bridge_length와 같아지면 트럭빼기
                t_list.pop() #시간을 더해줘야 할 것 같은데, 밑에 if, else 구문에서 시간을 넣어주면 된다.
                
            if (sum(t_list)+q_truck) <= weight :   # t_list의 합이 weight 이하이면 트럭을 계속 넣을 수 있다.    
                t_list.insert(0,q_truck)
                q_truck = 0
                answer +=1
            else :
                t_list.insert(0,0) # t_list에 트럭이 들어간 시간을 구하기 위해 0,0을 넣어준다
                answer +=1
           
    # 마지막에 다리에 들어간 트럭이 나가는 시간 더해주기
    answer = answer + bridge_length
    
    return answer

 

다른사람 코드 1개 (훨씬 간결하다)

 

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