[알고리즘 문제풀이] 프로그래머스 - 다리를 지나는 트럭

yourjin·2022년 3월 7일

level2 알고리즘 큐(Queue)

알고리즘 문제풀이

목록 보기

18/28

TIL (2022.02.23)

➕ 오늘 푼 문제

프로그래머스 - 다리를 지나는 트럭

➕ 아이디어

큐에 트럭을 추가할 수 있다면 트럭 무게를, 추가할 수 없다면 대신 0을 추가하는 과정을 반복한다. 큐에 있는 트럭의 무게 합이 0인 경우 반복을 종료한다.
(이때 트럭은 처음에 큐가 다 차지 않았을 때를 제외하고는 항상 bridge_length를 유지한다. 따라서 큐에 있는 트럭의 무게 합을 bridge_weight에 따로 저장해, 이 값이 0인 경우를 반복의 종료 조건으로 삼는다.)

큐(bridge)의 길이가 bridge_length와 같다면, 맨 앞에 있는 원소를 뺀다.
대기열의 첫번째 원소가 추가되어도 weight을 넘지 않는다면 큐에 추가한다.
무게를 초과한다면, 대기열의 원소를 제거하지 않고 0을 추가한다.
더 이상 다리에 남아있는 원소가 없다면( bridge_weigth==0 )반복을 종료한다.

➕ Java 코드

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int index = 0;
        Queue<Integer> bridge = new LinkedList<Integer>();
        int bridge_weight = 0;
        
        do{
            if(bridge.size() == bridge_length){
                int out_weight = bridge.poll();
                bridge_weight -= out_weight;
            }
            
            if(truck_weights.length > index && truck_weights[index] + bridge_weight <= weight){
                bridge.offer(truck_weights[index]);
                bridge_weight += truck_weights[index];
                index++;
            }else{
                bridge.offer(0);
            }
            
            answer += 1;
            
        }while(bridge_weight != 0);
        
        return answer;
    }
}

➕ Python 코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    truck_weights = deque(truck_weights)
    bridge = deque()
    bridge_weight = 0

    while True:
        if len(bridge) == bridge_length:
            out_weight = bridge.popleft()
            bridge_weight -= out_weight
            
        if truck_weights and truck_weights[0] + bridge_weight <= weight:
            next_weight = truck_weights.popleft()
            bridge.append(next_weight)
            bridge_weight += next_weight
        else:
            bridge.append(0)        
            
        answer += 1
        
        if bridge_weight == 0:
            break
            
    return answer

➕ 궁금한 내용 및 소감

어떻게 풀어야 하는 지는 명확하지만, 항상 어떻게 구현할 것인가가 가장 어려운 것 같다. 이 문제 또한 구현이 마음대로 안되서 여러 풀이를 참고했다. (결국은 그대로 따라하지는 않았지만 말이다.) 그래도 구현 파트는 많은 코드를 보고 연습하면 그만큼 늘 것이라고 생각한다! 다음번에 이 문제를 풀 때는 꼭 혼자 힘으로 풀 수 있기를 바란다.