[ 백준 17612 ] 쇼핑몰 (C++)

백준의 쇼핑몰(17612) 문제이다.

 

[ 문제풀이 ]

고객들이 계산대를 통해서 계산을 하고 쇼핑몰을 떠나가는 과정에서 쇼핑몰을 빠져나오는 고객의 순서를 구해야 하는 문제이다.

문제 해결을 위해 사용되는 자료구조부터 정답을 도출하기 위한 해결과정까지 진행해보자.

 

#1. 소문제로의 분리

본인은 이 문제를 작은 2개의 부분으로 나눠서 접근을 하였다.

1. 고객이 계산대에 들어가는 과정

2. 고객이 계산대에서 빠져 나오는 과정

이렇게 2개의 부분으로 나눠서 접근하였다. 왜냐하면, 고객이 계산대에 들어가는 과정에서 발생할 수 있는 여러 상황들에 대한 조건들과 계산대에서 빠져나가는 과정에서 발생할 수 있는 여러 상황들에 대한 조건이 약간의 차이가 있기 때문에 이와 같이 2가지 상황으로 나눠서 접근하였다.

 

그렇다면 위의 2가지 상황들에 대해서 구체적으로 진행해보자.

 

#2. 계산대에 들어가는 과정

먼저, 고객이 계산대에 들어가는 과정부터 살펴보자.

K개의 계산대가 병렬적인 구조로 존재하고, 안내원들은 가장 빨리 계산을 마칠 수 있는 계산대로 안내를 하고, 계산대에서 기다릴 시간이 똑같은 경우에는 계산대의 번호가 더 작은 계산대로 안내를 한다는 조건이 있다.

여기서 "가장 빨리 계산을 마칠 수 있는 계산대로 안내한다" 라는 것은 단순하게 "계산대가 가장 먼저 비는 곳으로 그 다음 손님을 안내한다" 라고 생각 하면 된다. 왜냐하면 손님이 계산하는데 걸리는 시간은 정해져 있고 계산대마다 계산하는 시간이 다른 것이 아니므로 빨리 계산대에 들어갈수록 빨리 계산이 끝나기 때문이다.

 

그럼 가장 먼저 K명의 고객은 계산대에 동시에 들어가게 될 것이다. 왜냐하면 처음 K개의 계산대는 모두 비어있는 상태일 것이기 때문이다. 문제는, 그 다음부터이다. 이제부터는 계산대가 비는 순서대로 손님을 안내해야하고 동시에 비는 계산대가 있다면 조건에 따라 더 작은 계산대 번호를 가진 계산대로 안내를 해야 한다.

정리해서 표현해보면, "계산이 더 빠르게 끝나는 계산대, 즉, 계산 시간이 가장 짧은 손님이 있는 계산대가 더 높은 우선순위를, 그런 계산대가 여러개라면 계산대의 번호가 더 낮은 계산대가 더 높은 우선순위를 갖게 된다" 라고 표현할 수 있다.

이를 위해서 본인은 우선순위큐를 사용해 주었다. 계산대를 우선순위큐 처럼 사용하는 것이다.

 

우선순위큐에서는 3개의 데이터를 관리해 주었다.

1. 손님의 번호

2. 계산하는데 걸리는 시간

3. 계산대의 번호

손님의 번호는 정답을 도출하기 위해서 알고 있어야 하는 정보이고, 계산하는데 걸리는 시간은 손님을 계산대에 안내하는 과정에서 어떤 계산대가 더 빨리 계산이 끝나는지를 비교하기 위해서 필요한 정보이고, 계산대의 번호는 계산이 동시에 끝나는 계산대가 발생할 경우 비교하기 위해서 필요한 정보이다. 그리고 조건에 맞게 우선순위큐의 비교조건을 설정해 주었다.

 

그럼, 가장 첫 K명의 손님을 계산대(Priority Queue)에 삽입하는 과정을 코드로 나타내 보면 다음과 같다.

	priority_queue<CUSTOMER, vector<CUSTOMER>, PQ_Cmp> PQ;
	bool Flag = false;
    
	for (int i = 0; i < K; i++)
	{
		if (i == N)
		{
			Flag = true;
			break;
		}
		int Custom_Num = Customer[i].first;
		int Custom_Time = Customer[i].second;
		PQ.push({ Custom_Num, Custom_Time, i + 1 });
	}

line6)에서 보면, 조건문이 하나 있다. 바로 계산대의 수 > 손님의 수인 경우이다.

쉽게 이야기해서, 손님이 3명이 있는데 계산대는 총 5개의 계산대가 있는 경우이다. 이 경우에는 K명의 손님을 계산대에 넣을 수 없기 때문에 탐색을 중단해 주어야 한다. 이를 위한 조건문이다.

 

그렇다면, 이제는 K명 이후의 손님들을 계산대에 넣는 과정을 알아보자.

우리가 계산대로 표현하고 있는 우선순위큐의 가장 top() 에는 어떤 값이 저장되어 있을까 ??

아마, "계산이 가장 일찍 끝나면서 동시에 계산대의 번호가 가장 작은 계산대" 가 있을 것이다. 왜냐하면 이러한 조건을 가진 우선순위큐에 데이터를 넣고 있기 때문이다.

그럼 지금부터는 top()에 있는 값들을 하나씩 빼면서 순차적으로 손님을 넣어주면 된다.

top()에 있는 값들을 하나씩 뺀다는 것은 "계산이 끝난 손님을 보내고 새로운 손님을 받는다" 라는 것과 같은 맥락이기 때문이다.

이 부분에 대한 코드는 밑에서 계산대에서 나오는 과정에 대해서 까지 진행한 후에 확인해보자.

 

#3. 계산대에서 나오는 과정

계산대에서 나오는 과정을 진행해보자. 본인은 계산대에서 나오는 손님의 정보를 관리하기 위한 Vector를 하나 만들어서 관리해 주었다. 그리고 #2에서 이야기했던, 우선순위큐에서 데이터를 하나씩 빼는 과정과 동시에 Vector에 해당 고객의 정보를 넣어주었다.

하지만, Vector를 그대로 출력을 해버리면 안된다. 왜냐하면 "동일 시간에 계산을 마친 고객이 존재한다면, 높은 계산대의 번호를 가진 고객이 먼저 빠져 나온다는 조건" 때문이다.

따라서, 이 Vector또한 마지막에 조건에 맞게 정렬을 한번 더 해주어야 한다.

#2와 #3의 과정을 코드로 나타내면 다음과 같다.

	priority_queue<CUSTOMER, vector<CUSTOMER>, PQ_Cmp> PQ;
	vector<CUSTOMER> Exit_Order;
	bool Flag = false;
    
	for (int i = 0; i < K; i++)
	{
		if (i == N)
		{
			Flag = true;
			break;
		}
		int Custom_Num = Customer[i].first;
		int Custom_Time = Customer[i].second;
		PQ.push({ Custom_Num, Custom_Time, i + 1 });
	}

	if (Flag == true)
	{
		while (PQ.empty() == 0)
		{
			Exit_Order.push_back(PQ.top());
			PQ.pop();
		}
	}
	else
	{
		for (int i = K; i < N; i++)
		{
			int Custom_Num = Customer[i].first;
			int Custom_Time = Customer[i].second;
			PQ.push({ Custom_Num, Custom_Time + PQ.top().Time, PQ.top().Counter_Number });
			Exit_Order.push_back(PQ.top());
			PQ.pop();
		}

		while (PQ.empty() == 0)
		{
			Exit_Order.push_back(PQ.top());
			PQ.pop();
		}
	}

	sort(Exit_Order.begin(), Exit_Order.end(), Cmp);

 

[ 소스코드 ]

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
struct CUSTOMER
{
    int Customer_Number;
    int Time;
    int Counter_Number;
};
 
int N, K;
vector<pair<int, int>> Customer;
 
struct PQ_Cmp
{
    bool operator()(CUSTOMER A, CUSTOMER B)
    {
        if (A.Time == B.Time)
        {
            if (A.Counter_Number > B.Counter_Number)
            {
                return true;
            }
            return false;
        }
        else
        {
            if (A.Time > B.Time)
            {
                return true;
            }
            return false;
        }
    }
};
 
bool Cmp(CUSTOMER A, CUSTOMER B)
{
    if (A.Time == B.Time)
    {
        if (A.Counter_Number > B.Counter_Number)
        {
            return true;
        }
        return false;
    }
    else
    {
        if (A.Time < B.Time)
        {
            return true;
        }
        return false;
    }
}
 
void Input()
{
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        int a, b; cin >> a >> b;
        Customer.push_back(make_pair(a, b));
    }
}
 
void Solution()
{
    priority_queue<CUSTOMER, vector<CUSTOMER>, PQ_Cmp> PQ;
    vector<CUSTOMER> Exit_Order;
    bool Flag = false;
    for (int i = 0; i < K; i++)
    {
        if (i == N)
        {
            Flag = true;
            break;
        }
        int Custom_Num = Customer[i].first;
        int Custom_Time = Customer[i].second;
        PQ.push({ Custom_Num, Custom_Time, i + 1 });
    }
 
    if (Flag == true)
    {
        while (PQ.empty() == 0)
        {
            Exit_Order.push_back(PQ.top());
            PQ.pop();
        }
    }
    else
    {
        for (int i = K; i < N; i++)
        {
            int Custom_Num = Customer[i].first;
            int Custom_Time = Customer[i].second;
            PQ.push({ Custom_Num, Custom_Time + PQ.top().Time, PQ.top().Counter_Number });
            Exit_Order.push_back(PQ.top());
            PQ.pop();
        }
 
        while (PQ.empty() == 0)
        {
            Exit_Order.push_back(PQ.top());
            PQ.pop();
        }
    }
 
    sort(Exit_Order.begin(), Exit_Order.end(), Cmp);
    long long Answer = 0;
    for (int i = 0; i < Exit_Order.size(); i++)
    {
        int Number = Exit_Order[i].Customer_Number;
        long long Result = (long long)((i + 1)) * (long long)Number;
        Answer += Result;
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    //freopen("Input.txt", "r", stdin);
    Solve();
    return 0;
}