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

[문제]

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

 

 

[풀이]

 

다리의 상황을 시뮬레이션하는 코드로 구현했다.

 

1. 현재 다리에 트럭이 있으면, 트럭들에 대한 시간 경과를 체크해준다.

2. 다리에 트럭을 올리는 작업을 실시한다. 세 조건을 만족해야만 다리에 트럭을 올릴 수 있다.

  2-1. 현재 다리에 존재하는 트럭 무게의 합이 견딜 수 있는 무게보다 작은 경우

  2-2. 다리 길이보다 현재 트럭 갯수가 적을 경우

  2-3. 아직 올라가지 못한 트럭이 있을 경우

3. 모든 트럭이 다리에 올라갈 경우, 시뮬레이션 종료 준비를 하기 위해 bool값을 활용했다.

4. 모든 트럭이 다리를 지난 경우, 반복문을 탈출하면서 시뮬레이션 1회당 1씩 증가시켜줬던 answer를 리턴한다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

struct Bridge
{
    int Weight = 0;
    int Time = 0;
};

// 모든 트럭이 다리를 건너려면 몇 초기 필요한지 알아내기
// bridge_length : 트럭이 올라갈 수 있는 최대 갯수
// weight : 견딜 수 있는 무게, 이하로 트럭이 있어야함
int solution(int bridge_length, int weight, vector<int> truck_weights)
{
    int answer = 0;
    int Time = 0;
    int CurWeight = 0;
    vector<Bridge> Bridges;
    queue<int> Trucks;
    for (int Value : truck_weights)
    {
        Trucks.push(Value);
    }

    bool IsAll = false;
    bool IsBreak = false;

    while (true)
    {
        ++answer;
        for (int i = 0; i < Bridges.size(); i++)
        {
            Bridges[i].Time += 1;
            // 시간 다됐으면 꺼내기
            if (Bridges[i].Time > bridge_length)
            {
                CurWeight -= Bridges[i].Weight;
                Bridges.erase(Bridges.begin());
                i--;

                if (IsAll && 0 == Bridges.size())
                {
                    IsBreak = true;
                    break;
                }
            }
        }

        if (IsBreak) break;

        if (!Trucks.empty() && CurWeight + Trucks.front() <= weight && Bridges.size() < bridge_length) // 현재 다리에 존재하는 트럭 무게 합이 견딜 수 있는 무게보다 적을 때, 다리 길이보다 현재 트럭 갯수 적을 때, 올리기 가능
        {
            int Weight = Trucks.front();
            Trucks.pop();
            CurWeight += Weight;
            Bridges.push_back({ Weight, 1 });
        }

        if (Trucks.empty())
        {
            IsAll = true;
        }
    }

    return answer;
}