[LV2 스택/큐] 다리를 지나는 트럭

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

프로그래머스

 

 

[풀이]

---

# deque로 구현
# queue를 bridge_length만큼 만든 뒤
# queue의 총합이 weight보다 낮을 경우
# truck_weights를 하나씩 다리 위로 올린다(queue에 올린다)
    # 올라갔을 때는 항상 하나씩 작아지면서 맨 뒤에껄 0으로 업데이트해야함
    # popleft를 하고, 뒤에 append로 쌓아야함
    # 하지만 popleft할 때 append는 항상 0으로만 하면 됨
# 마지막에 sum 했을 때 0이면 종료

from collections import deque

def solution(bridge_length, weight, truck_weights):
    cnt = 0
    queue = [0] * bridge_length
    queue = deque(queue)
    
    on_weights = 0 
    while len(queue) != 0:
        if len(truck_weights) != 0:
            
            # queue에 맨 앞에 값이 들어오면 빼줘야한다.
            # 곧 나갈 것이기 때문에 다리 위에 올릴 수 있음
            # on_weights에는 항상 올린 무게와 내린 무게를 연산
            if on_weights + truck_weights[0] - queue[0] <= weight:
                on_weights += truck_weights[0]
                on_weights -= queue[0]
                queue.popleft()
                queue.append(truck_weights.pop(0))
                cnt += 1
            
            # 못 올리면, 그냥 다리에서 내리는 작업 시행
            # 어차피 queue의 첫번째가 0이면 연산에 이상 없기 때문에, 그냥 조건 없이 뺌
            else :
                on_weights -= queue[0]
                queue.popleft()
                queue.append(0)
                cnt += 1
        
        # truck_weights가 없으면 이제 0 안넣고 큐에서 빼내기만 하는 연산
        else :
            on_weights -= queue[0]
            queue.popleft()
            cnt += 1
            
    return cnt

• 큐를 이용한 알고리즘
• [0]을 곱한 배열을 deque로 전환해서
• 매번마다 다리의 무게와 차들의 무게를 비교해서 다리 하중보다 낮으면 투입
• 다른 경우엔 queue의 맨 앞 부분을 제외하고 맨 뒤에 0을 추가해주면서, 간격을 맞춘다.
• else일 때는 popleft해서 뒤에서 빼내기만 하는 연산을 진행한다.
• queue의 개수가 0이 될 때 끝내기

 

[풀이 후기]

---

스택/큐는 머릿속에서 돌긴 하는 것 같다. 가장 직관적인 것 같기도 하다. 고득점 킷 다 풀어보주아!!