백준 5464 - 주차장 (C++)

 

 

주차장에는 주차 공간이 N개만큼 있다.

이 주차장에는 오늘 하루동안 M개의 자동차가 주차와 출차를 반복할 예정이다.

 

각 주차 공간에는 번호가 부여되어 있으며, 주차 공간 별로 요금이 상이하다.

요금의 기준은 자동차의 무게이며, 단위 무게당 받아야 하는 금액이 주차 공간별로 책정되어 있다.

 

예를 들어, 1번 주차공간이 단위 무게당 3원의 요금을 받는다면 200의 무게를 가진 자동차는 1번 주차공간에 주차하게 되면 200 * 3인 600원의 요금을 지불해야 하는 것이다.

 

주차를 하고자 하는 자동차는 비어있는 주차 공간중 가장 번호가 낮은 공간에 우선적으로 주차를 해야한다.

1, 3, 5번의 공간이 비어있다면 자동차는 무조건 1번에 주차를 해야하는 것이다.

 

하지만, 주차공간이 모두 꽉차있는 경우도 있을 수 있는데 이 경우엔 별도의 대기구역에 자동차가 들어온 순서대로 대기를 하게 되며 기존의 자동차가 출차하여 주차 공간이 새로 생길 경우, 대기구역에 먼저 들어온 자동차가 우선적으로 새로운 주차공간에 주차를 하게 된다.

 

이 규칙으로 주차장을 운영했을 때, 하루동안 주차장이 벌어들일 총 수익을 출력하면 되는 문제이다.

 

문제 풀이

문제를 이해하는 것이 다소 헷갈리지만, 이해만 한다면 그대로 구현하면 되는 문제이다.

본인은 해당 주차장을 구현하기 위해, 1개의 우선순위 큐, 2개의 큐, 2개의 벡터를 선언하였다.

 

우선순위 큐는 현재 비어있는 주차공간의 번호와 해당 주차공간의 단위무게당 요금을 pair로 담고있다.

두개의 큐는 대기공간에 들어온 차량의 순서를 저장하는 큐 한개와 주차, 출차기록을 담고있는 큐 한개이다.

두개의 벡터는 차량 번호별 무게를 담고있는 벡터 한개와, 현재 차량이 주차하고 있는 주차공간의 정보를 담고있는 벡터이다.

 

주차, 출차 과정은 아래와 같다.

 

1.먼저 주차,출차 기록을 담은 큐에서 가장 위의 원소를 꺼내어 확인해준다.

 

2 - 1.해당 값이 양수라면 비어있는 주차공간을 담은 우선순위 큐에서 가장 위의 원소를 꺼내어, 해당 공간에 차량을 주차한다. (만약, 비어있는 주차공간이 없다면 대기공간 큐에 차량을 삽입하여준다.)

 

2 - 2. 해당 값이 음수라면, 차량이 주차되어있는 주차 공간의 정보를 참조하여 요금을 계산한 뒤 총 수익에 더해준다.

(이 때, 대기공간 큐에 차량이 1개이상 있다면, 가장 위의 차량을 꺼내어 해당 주차공간에 주차해준다.)

 

3. 주차, 출차 기록을 담은 큐의 원소가 사라질때까지 반복한다.

 

4. 총 수익을 출력해준다.

 

위의 과정을 거치면, 문제는 간단하게 해결된다.

 

풀이 코드

int NumOfSpace = 0;
int NumOfCar = 0;
std::cin >> NumOfSpace >> NumOfCar;

  먼저, 주차 공간의 수와 차량의 수를 입력받아 준다.

 

std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> Spaces;
for (int i = 0; i < NumOfSpace; i++)
{
    int Price = 0;
    std::cin >> Price;

    Spaces.push({ i + 1, Price });
}

이후, 우선순위 큐를 하나 선언하여 주차공간의 번호와 가격을 저장해준다.

이 때, 우선순위 큐는 주차 공간의 번호가 작은 원소가 더 앞에 있도록 정렬되어야 한다.

 

std::vector<int> CarWeights(NumOfCar + 1);
for (int i = 1; i <= NumOfCar; i++)
{
    std::cin >> CarWeights[i];
}

std::queue<int> InAndOut;
for (int i = 0; i < 2 * NumOfCar; i++)
{
    int Record = 0;
    std::cin >> Record;
    InAndOut.push(Record);
}

다음은 자동차의 무게와 주차,출차기록을 입력받아서 저장해준다.

 

std::vector<std::pair<int, int>> CarStopSpace(NumOfCar + 1);
std::queue<int> WaitQueue;

자동차가 현재 주차되어 있는 공간의 정보를 저장하는 벡터와 대기 차량을 담을 큐를 선언해주었다.

 

int Revenue = 0;
while (InAndOut.size() > 0)
{
    int CurRecord = InAndOut.front();
    InAndOut.pop();

    if (CurRecord > 0)
    {
        if (Spaces.size() == 0)
        {
            WaitQueue.push(CurRecord);
        }
        else
        {
            CarStopSpace[CurRecord] = Spaces.top();
            Spaces.pop();
        }
    }
    else
    {
        int CurCar = abs(CurRecord);
        Spaces.push(CarStopSpace[CurCar]);

        Revenue += CarStopSpace[CurCar].second * CarWeights[CurCar];

        if (WaitQueue.size() > 0)
        {
            CarStopSpace[WaitQueue.front()] = Spaces.top();
            Spaces.pop();
            WaitQueue.pop();
        }
    }
}

 

위에서 말한 과정을 반복문으로 구현하였다.

먼저, 총 수익을 저장할 Revenue 변수를 선언하였다.

 

이후 주차, 출차 기록이 담긴 큐에서 원소를 하나씩 빼며 검사하도록 하였으며 해당 큐의 원소가 모두 사라지면 반복문을 종료하도록 하였다.

 

반복문 내에서는 먼저 현재 주차, 출차 기록이 양수인지 음수인지를 확인하여 주차인지 출차인지를 판별하였다.

 

만약 주차라면, 비어있는 주차공간이 있나 없나를 판단한 뒤, 주차공간이 있다면 해당 영역에 차량을 주차해주었고, 비어있는 공간이 없다면 대기차량에 차량을 삽입해주었다.

 

차량을 주차했기 때문에, 비어있는 주차공간을 담고 있는 Space의 가장 위의 원소를 pop하였으며, 차량이 주차된 공간의 정보를 담은 CarStopSpace의 값을 해당 주차공간의 값으로 갱신해주었다.

 

반대로, 현재 기록이 출차라면 차량의 무게와 주차공간의 요금을 참조하여 총 요금을 계산한 뒤 Revenue에 더해주었다.

그리고 이 때, 주차공간이 하나 비게 되므로 대기하고 있는 차량이 있다면 해당 차량을 주차해주도록 하였다.

 

std::cout << Revenue;

return 0;

 

모두 끝나고, Revenue를 출력해주면 문제 해결이다.

 

 

코드 전문

#include <iostream>
#include <vector>
#include <queue>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumOfSpace = 0;
    int NumOfCar = 0;
    std::cin >> NumOfSpace >> NumOfCar;
    
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> Spaces;
    for (int i = 0; i < NumOfSpace; i++)
    {
        int Price = 0;
        std::cin >> Price;

        Spaces.push({ i + 1, Price });
    }
    
    std::vector<int> CarWeights(NumOfCar + 1);
    for (int i = 1; i <= NumOfCar; i++)
    {
        std::cin >> CarWeights[i];
    }

    std::queue<int> InAndOut;
    for (int i = 0; i < 2 * NumOfCar; i++)
    {
        int Record = 0;
        std::cin >> Record;
        InAndOut.push(Record);
    }

    std::vector<std::pair<int, int>> CarStopSpace(NumOfCar + 1);
    std::queue<int> WaitQueue;

    int Revenue = 0;
    while (InAndOut.size() > 0)
    {
        int CurRecord = InAndOut.front();
        InAndOut.pop();

        if (CurRecord > 0)
        {
            if (Spaces.size() == 0)
            {
                WaitQueue.push(CurRecord);
            }
            else
            {
                CarStopSpace[CurRecord] = Spaces.top();
                Spaces.pop();
            }
        }
        else
        {
            int CurCar = abs(CurRecord);
            Spaces.push(CarStopSpace[CurCar]);

            Revenue += CarStopSpace[CurCar].second * CarWeights[CurCar];

            if (WaitQueue.size() > 0)
            {
                CarStopSpace[WaitQueue.front()] = Spaces.top();
                Spaces.pop();
                WaitQueue.pop();
            }
        }
    }

    std::cout << Revenue;

    return 0;
}