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

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

프로그래머스

🤔 문제분석

덱큐를 이용하여 문제를 해결 하였습니다.

덱큐를 트럭을 담고있는 큐로 생각하고 0을 담고있다면 트럭은 없고 1 이상일경우 트럭이 있다고 가정합니다.

1. 처음에 모든 큐를 다리 길이만큼 0으로 채워 줍니다.
2. 트럭을 순회하면서 넣어봅니다.
   1. 덱의 마지막에 트럭이 존재한다면 현재무게와 현재 카운트를 뺍니다.
   2. 현재무게와 현재카운트를 만족시키는 트럭을 넣을 수 있다면 넣습니다. 넣지 못한다면 0을 넣습니다.
   3. 모든 트럭을 순회하면서 다 넣으면 반복문을 종료합니다.
   4. 리터레이션당 시간을 계속 증가시킵니다.
3. 덱큐에 있는 모든 값을 pop 시키면서 시간을 증가시킵니다.

💻 코드

파이썬

# <https://school.programmers.co.kr/learn/courses/30/lessons/42583?language=python3>
from collections import deque

def solution(bridge_length, weight, truck_weights):
    
    current_cnt = 0
    current_weight = 0
    answer = 0
    
    q = deque()
    
    for _ in range(bridge_length):
        q.append(0)
        
    i = 0
    while len(truck_weights) > i:
        truck = q.pop()
        if truck > 0:
            current_cnt -= 1
            current_weight -= truck
            
        current_truck = truck_weights[i]
        # 트럭이 다리에 올라갈 수 있다면
        if weight >= current_truck + current_weight and bridge_length >= current_cnt + 1:
            current_cnt += 1
            current_weight += current_truck
            q.appendleft(current_truck)
        else:
            q.appendleft(0)
            i -= 1

        i += 1
        answer += 1
        
    while q:
        q.pop()
        answer += 1
        
    return answer

C++

#include <string>
#include <vector>
#include <deque>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {

    int answer = 0;
    int currentWeight = 0;
    int currentCnt = 0;
    deque<int> q;

    for(int i = 0; i < bridge_length; i ++)
    {
        q.push_back(0);
    }

    for(int i = 0; i < truck_weights.size(); i ++)
    {
        // 마지막 deque에서 트럭을 꺼낸다. 트럭이 있다면 무게와 개수를 줄이고 없다면 무시
        int truck = q.back();
        q.pop_back();
        // 트럭이 존재한다면
        if(truck > 0) {
            currentWeight -= truck;
            currentCnt -= 1;
        }

        // 주어진 조건에 만족하면 트럭을 추가한다.
        int new_truck = truck_weights[i];
        if(weight >= currentWeight + new_truck && bridge_length >= currentCnt + 1) {
            q.push_front(new_truck);
            currentWeight += new_truck;
            currentCnt += 1;
        }
        // 넣을 수 없는 트럭이 없다면 다음 리터레이션에서 트럭을 넣을 수 있게 i를 증감한다.
        else {
            q.push_front(0);
            i -= 1;
        }

        answer += 1;
    }

    while(!q.empty())
    {
        q.pop_back();
        answer += 1;
    }

    
    return answer;
}

Java

package Algorithm.java.다리를지나는트럭;

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int currentWeight = 0;
        int currentCnt = 0;

        // 다리에 트럭의 정보를 담는다.
        Deque<Integer> bridge = new ArrayDeque<>();
        for(int i = 0; i < bridge_length; i ++)
        {
            bridge.add(0);
        }

        // 트럭을 순회하면서 다리에 넣는다.
        for(int i = 0; i < truck_weights.length; i++)
        {
            // 끝에 트럭이 존재한다면 트럭을 도착시킨다.
            Integer truck = bridge.pollLast();
            if(truck > 0)
            {
                currentWeight -= truck;
                currentCnt -= 1;
            }

            // 현재 트럭을 넣을 수 있다면 트럭을 넣는다.
            if(weight >= currentWeight + truck_weights[i] && bridge_length >= currentCnt + 1) {
                bridge.addFirst(truck_weights[i]);
                currentWeight += truck_weights[i];
                currentCnt += 1;
            }
            else {
                // 다음 리터레이션에서 다시 트럭을 넣어야하기때문에 Dummy를 넣고 i를 증감한다.
                bridge.addFirst(0);
                i--;
            }
            answer += 1;
        }

        // 남은 트럭을 꺼낸다.
        while(!bridge.isEmpty())
        {
            bridge.pollLast();
            answer += 1;
        }

        return answer;
    }
}